Taking vector transposes seriously

Introduction

The thesis of this paper is as follows:

Users want to write, using compositions of the transpose and product operators, linear algebra expressions that involve vectors and matrices, and the results make sense, i.e. the results of u'*v behaves like a scalar. Examples of linear algebraic expressions users expect to write include:

Inner product \(u^{T}v\), a scalar,

Outer product \(uv^{T}\), a matrix,

Quadratic form \(u^{T}Au\), a scalar,

Bilinear form \(u^{T}Av\), a scalar,

The description of these quantities employ Householder notation (Householder 1953, Householder 1955), a convention that is familiar to most, if not all, practitioners of numerical linear algebra today.

Introduction (v1)

Humans, to a fault, are so good at special casing abstractions by context that it would be easy to conclude that a discussion of how linear algebra fits into computer languages would hardly seem necessary. Decades after APL made multidimensional arrays first class objects, and MATLAB made matrix laboratory syntax popular, we recently reached an inescapable conclusion, one we preferred not to believe, that vectors, in the sense of computer languages, and linear algebra vectors have serious coexistence issues.

To set the stage, in nearly every computer language (other than MATLAB (!!)) a “vector” is a one dimensional container. In concrete linear algebra there are column vectors and row vectors. In both concrete and abstract linear algebra, vectors are quantities that are subject to addition, multiplication by scalars, linear transformations, and play a role in scalar and outer products. As we shall see, the seemingly innocuous idea of transposing a vector turns out to be a highly contentious subject.

Consider the following familiar statements

  • A matrix times a vector is a vector

  • Matrix Multiplication of \(A\) and \(B\) is defined by taking the scalar product of a row of \(A\) with a column of \(B\).

  • The scalar product is defined on a pair of vectors. The scalar product of \(v\) with itself is a non-negative number known as \(\|v\|^{2}\).

and consider common notations in math or software:

  • A[i,:]*B[:,j] or dot(A[i,:],B[:,j])

  • \(v^{T}\!v=(v,v)=\) v'*v =dot(v,v)

(more coming)

Introduction (v0)

Matrices and vectors are fundamental concepts for both computer science  (Knuth 1967, Pratt 2001) and computational science (Strang 2003, Trefethen 1997). Nevertheless, the terms “vector” and “matrix” mean different things in the contexts of data structures and linear algebra. As data structures, they are simply arrays, whereas as linear algebraic objects, vectors are elements of a vector space and matrices are linear transformations. When we represent linear algebra vectors and linear algebra transformation in a basis, we obtain the familiar containers we know simply as vectors and matrices.

Computer science focuses primarily on the homogeneous container semantics of vectors and matrices. Oftentimes they are considered synonymous with arrays of rank 1 and 2 respectively. The seminal work of (Iliffe 1961) says

“Depending on the organization of the array it may be treated as a set, a vector, or a matrix.”

The classic (Knuth 1967) focuses only on indexing semantics; the index entry for “two-dimensional array” cross-references the entry for “matrix”. Even today, the conflation persists. A modern textbook on programming language design writes (p. 215 Pratt 2001):

A vector is a one-dimensional array; a matrix composed of rows and columns of components is a two-dimensional array[.]

In contrast, vectors and matrices in linear algebra are defined by their algebraic properties, such as inner products and matrix-vector products.

The aim of this paper is to identify if and when the semantics of array indexing and linear algebra may conflict.