Authorea

Jiahao Chen Reorganized with timeline and more references over 8 years ago

Commit id: 42ce91b98e141edefcb37340d975fea666b68650

deletions | additions

@book{Gantmacher1960, @book{Grassmann1844, address = {New York, NY}, {Leipzig}, author = {Gantmacher, F R}, {Grassmann, Hermann}, publisher = {Chelsea}, volume {Verlag von Otto Wigand}, title = {Die lineale {A}usdehungslehre}, year = {1844}, url = 1, {https://archive.org/details/dielinealeausde00grasgoog} } @article{Hamilton1847, author = {William Rowan Hamilton}, title = {On Symbolical Geometry}, journal = {The theory Cambridge and Dublin Mathematical Journal}, publisher = {Macmillan, Barclay and Macmillan}, editor = {W. Thompson}, volume = II, year = 1847, pages = {130-133}, url = {http://www.emis.ams.org/classics/Hamilton/SymGeom.pdf}, address = {Cambridge} } @book{Grassmann1862, address = {Berlin}, author = {Grassmann, Hermann}, publisher = {Verlag von Th. Chr. Fr. Enslin}, title = {Die {A}usdehnungslehre}, url = {https://archive.org/stream/dieausdehnungsl05grasgoog}, year = {1862} } @article{Peirce1873, title = {Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of {B}oole's Calculus of Logic}, author = {C. S. Peirce}, journal = {Memoirs of the American Academy of Arts and Sciences}, series = 2, volume = 9, number = 2, year = 1873, pages = {317-378}, doi = {10.2307/25058006}, url = {http://www.jstor.org/stable/25058006} } @article{Peirce1874, title = {On the Uses and Transformations of matrices}, Linear Algebra}, author = {Benjamin Peirce}, journal = {Proceedings of the American Academy of Arts and Sciences}, volume = 10, year = {1874-1875}, pages = {395-400}, doi = {10.2307/20021428}, URL = {http://www.jstor.org/stable/20021428} } @article{Peirce1883, title = {A Communication from {M}r. {P}eirce}, author = {C. S. Peirce}, journal = {Johns Hopkins University Circulars}, volume = II, number = 22, year = {1960} 1883, pages = {86-88}, url = {https://jscholarship.library.jhu.edu/handle/1774.2/32850} } @article{Weierstrass1884, Author = {Karl Weierstrass}, title = {Zur {T}heorie der aus $n$ {H}aupteinheiten gebildeten komplexen {G}rössen}, Journal = {Nachrichten von der Königlichen Gesellschaft der Wissenschaften und der Gerog-Augusts-Universität zu Göttingen}, number = 10, year = 1884, pages = {395--414}, url = {https://archive.org/details/nachrichtenvond44gtgoog} } @article{Dedekind1885, Author = {E Dedekind}, title = {Zur {T}heorie der aus $n$ {H}aupteinheiten gebildeten komplexen {G}rössen}, Journal = {Nachrichten von der Königlichen Gesellschaft der Wissenschaften und der Gerog-Augusts-Universität zu Göttingen}, number = 4, year = 1885, pages = {141--}, url = {https://archive.org/details/nachrichtenvond43gtgoog} } @article{Scheffers1889, Author = {Georg Wilhelm Scheffers}, title = {Zur {T}heorie der aus $n$ {H}aupteinheiten gebildeten komplexen {G}rössen}, Journal = {Berichte über die Verhandlungen der Königlich Sächsischen Gesellschaft der Wissenschaften zu Leipzig. Mathematisch-Physische Classe.}, url = {http://babel.hathitrust.org/cgi/pt?id=uc1.b5383367}, address = Leipzig, publisher = {Breitkopf \& Härtel}, year = 1889, pages = {290--307} } @book{MacDuffee1933, Address = {Berlin}, Author = {MacDuffee, Cyril Colton}, Publisher = {Verlag von Julius Springer}, Title = {The Theory of Matrices}, Year = {1933}, doi= {10.1007/978-3-642-99234-6} } @book{Gantmacher1960, Address = {New York, NY}, Author = {Gantmacher, F R}, Publisher = {Chelsea}, Title = {The theory of matrices}, Volume = 1, Year = {1960}} @book{Apostol1967, Address = {New York, NY}, Author = {Tom M Apostol}, Editor = {George Springer}, Publisher = {John Wiley & \& Sons}, Title = {Calculus}, Volume = {1}, Year = {1967} } {1967}} @book{Apostol1969, Address = {New York, NY}, Author = {Tom M Apostol}, Editor = {George Springer}, Publisher = {John Wiley & \& Sons}, Title = {Calculus}, Volume = {2}, Year = {1969} } {1969}} @book{Wilson1947, @book{Wilson1901, Address = {New Haven, CT}, Author = {Edwin Bidwell Wilson}, Publisher = {Yale University}, Title = {Vector Analysis}, Url = {https://archive.org/stream/117714283}, Year = {1947}} {1901}, url = {https://archive.org/stream/117714283} } @book{Gibbs1881, Address = {New Haven, CT}, Author = {Josaiah Willard Gibbs}, Publisher = {Tuttle, Morehouse and Taylor}, Title = {Elements of Vector Analysis Arranged for the Use of Students in Physics}, Url = {https://archive.org/stream/elementsvectora00gibbgoog}, Year = {1881-4}} {1881-4}, url = {https://archive.org/stream/elementsvectora00gibbgoog} } @techreport{Householder1955, Address = {Oak Ridge, TN}, Author = {Alston S Householder}, Institution = {Oak Ridge National Laboratory}, Number = {ORNL-1883}, Title = {On the convergence of matrix iterations}, Url = {http://catalog.hathitrust.org/Record/007841779}, Year = {1955}} {1955}, url = {http://catalog.hathitrust.org/Record/007841779}} @book{Householder1953, Address = {New York, NY},

Series = {International Series in Pure and Applied Mathematics}, Serieseditor = {William Ted Martin}, Title = {Principles Of Numerical Analysis}, Url = {https://archive.org/stream/principlesofnume030218mbp}, Year = {1953}} {1953}, url = {https://archive.org/stream/principlesofnume030218mbp}} @book{Randell1964, Address = {London}, Author = {Randell, B and Russell, L J}, Publisher = {Academic Press}, Series = {The Automatic Programming Information Centre Studies in Data Processing}, Title = {{ALGOL {{ALGOL} 60 Implementation}}, Implementation}, Year = {1964}} @manual{Backus1956,

Author = {J W Backus and R K Beeber and S Best and R Goldberg and R A Hughes and L B Mitchell and R A Nelson and R Nutt and D Sayre and P B Sheridan and H Stern and I Ziller}, Organization = {International Business Machines Corporation}, Title = {Fortran Automatic Coding System for the {IBM 704 EDPM}: Programmer's Reference Manual}, Url = {https://www.fortran.com/FortranForTheIBM704.pdf}, Year = {1956}} {1956}, url = {https://www.fortran.com/FortranForTheIBM704.pdf} } @book{Grassmann1995, author = {Hermann Grassmann}, title = {A new branch of mathematics : the "{A}usdehnungslehre" of 1844 and other works}, publisher = {Open Court}, address = {Chicago}, year = 1995 } @book{Grassmann2000, author = {Hermann Grassmann}, series = {History of mathematics}, number = 19, title = {Extension theory}, publisher = {American Mathematical Society and London Mathematical Society}, address = {Providence, RI}, year = 2000, }

% Packages and macros go here \usepackage{lipsum} \usepackage{amsfonts} \usepackage{graphicx} \usepackage{epstopdf} \usepackage{algorithmic} \usepackage[utf8]{inputenc} %\usepackage{graphicx} %\usepackage{epstopdf} %\usepackage{algorithmic} \ifpdf \DeclareGraphicsExtensions{.eps,.pdf,.png,.jpg} \else

\fi % Declare title and authors, without \thanks \newcommand{\TheTitle}{\include{title}} \newcommand{\TheTitle}{Taking vector transposes seriously} \newcommand{\TheAuthors}{J. Chen and A. S. Edelman} % Sets running headers as well as PDF title and authors

% Authors: full names plus addresses. \author{ Jiahao Chen Chen\thanks{Department of Mathematics, and The Computer Science And Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA (\email{[email protected]}, \email{[email protected]}, \url{http://jiahao.github.io})} \and Alan S. Edelman\thanks{Department of Mathematics, and The Computer Science And Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA (\email{\{jiahao,edelman\}@mit.edu})}, Edelman\footnotemark[2] } \usepackage{amsopn}

% The next statement enables references to information in the % supplement. See the xr-hyperref package for details. \externaldocument{ex_supplement} %\externaldocument{ex_supplement} % FundRef data to be entered by SIAM %

68Q25, 68R10, 68U05 \end{AMS} \include{include} \input{include} \section*{Acknowledgments} Julia is an open source programming language freely available from \href{http://julialang.org}. \url{http://julialang.org}. We thank the many Julia users and developers who have contributed to the lively discussion of GitHub issue \href{https://github.com/JuliaLang/julia/issues/4774}{JuliaLang/julia/4774},

\item Quadratic/Hermitian forms, $v^\prime A v$ \end{itemize} The notation for these quantities were systematized by Householder \cite{Householder1953,Householder1955}, who used capital Roman letters for matrices, small Roman letters for (column) vectors, and small Greek letters for scalars. Importantly, Householder also uses the vector transpose notation $u^\prime$ to express row vectors, which are then used to construct the above products and forms. \cite{Householder1955} uses $u^T = (u_1, \cdots, u_n)^T$ to express row vectors as tuples, a construct which we shall see later as having ample precedent. \cite{Householder1955} writes the inner product as $u^* v$, noting that $*$ ``denotes the conjugate transpose''. \cite[Sec. 4.01]{Householder1953} introduces the Hermitian form . \cite[Sec. 2.04]{Householder1953} introduces the row vector $u^T$ corresponding to the column vector $u$. Householder also acknowledges in \cite[Sec. 2.04]{Householder1953} the analogy between a numerical vector (as a column of a matrix) and a geometric vector in the sense of Gibbs. He writes the vector transpose as if it follows immediately from the matrix transpose: If each column of a matrix $M$ is written as a row, the order remaining the same, the resulting matrix is known as the transpose of the original and is designated $M^T$. In particular, if $x$ is the column vector of the $\xi_i$, $x^T$ is the row vector of the $\xi_i$. The outer product shows up in \cite[Sec. 2.24]{Householder1953}, although Householder does not give the quantity $u v^T$ a special name \footnote{while \cite[Sec. 2.03]{Householder1953} introduces ``outer products'' $[u v]$ , these quantities are known today as bivectors and are conventionally denoted $u \wedge v$.}, and the discussion in context clearly implies that Householder considers vector-scalar-vector products $u \sigma v^T$ special cases of matrix products $U S V^T$. Interstingly, \cite{Householder1953} does not use the terms ``bilinear form'', ``quadratic form'', or ``Hermitian form''. He uses ``scalar product''. \cite{Householder1955} clearly spells out his notational convention. (\cite{Householder1953} has a missing page which might also spell it out, but it's not clear.) \subsection{History} \begin{tabular}{l} Mostly matrices \\ \hline Cullis (1913-28) \\ \end{tabular} \begin{tabular}{l} Mostly vectors \\ \hline Grassmann (1842-1866) \\ \end{tabular} \begin{tabular}{l} Matrices are primary \\ \hline Macduffee (1933) \\ Fadeev and Faddeeva (1959) \\ \end{tabular} \begin{tabular}{l} Vectors are primary \\ \hline \end{tabular} \section{A timeline of the development of key ideas} A rough sketch. \paragraph{Möbius (1827), Calcolo geometrico} May have introduced the scalar product \paragraph{Grassmann (1844) - Ausdehnungslehre I} Vectors were called ``extensive magnitudes''. Relative vectors were called ``displacements'' (,,Strecke``) (\S 14) and were distinguished from absolute vectors, being coordinates of points. Systematic convention: Capital Roman letters were names of points (absolute vectors). Small Roman letters were names of displacements (relative vectors). Ausdehnungslehre I introduced the ``open product'' (,,offne Produkt``) (\S 172) as the quantity \[ S = [A_1().B_1 + A_2().B_2 + \dots] \] or in modern notation, what we recognize today as the expansion of a matrix $S$ in rank-1 outer products \[ S = \sum_i b_i a_i^T \] A single term, written $[A().B]$ in Grassmann's notation, is a ,,Produkt mit ein Lücke`` (product with one opening), which is generalized to multiple openings in Ausdehnungslehre II. Such a single time is what we would today call an outer product of two vectors, or a rank 1 matrix. Ausdehnungslehre I introduces the concept of outer multiplication (,,äussere Multiplikation``) (\S 34, p.57, p.81English) as what we would today call the exterior product or wedge product. The term ``outer product'' (,,äusseres Produkt``) appears in \S 36, p. 60, p. 84English. \paragraph{Grassmann (1847)~\cite{Grassmann1847} - ,,Geometrische Analyse``} \S 7 p. 334 English, introduces the inner product $a \times b$, and the inner square $a^2 = a \times a$. \paragraph{Hamilton (1847)~\cite{Hamilton1847} - ``On Symbolical Geometry''} Introduces the term ``scalar product'' as part of the quaternion product. \S. 12 introduces the term ``scalar product'' for the case of parallel vectors (which differs from modern usage by a negative sign). He does not appear to have introduced the general case of non-parallel vectors. \paragraph{Cauchy (1853)~\cite{Cauchy1853}.} clefs algébriques??? influenced Grassmann 1862 for notation in the inner product??? \paragraph{Cayley (1858)~\cite{Cayley1858}} - invented matrix product and matrix transpose. Notation for matrix: \begin{verbatim} ( a, b, c) | d, e, f| | g, h, i| \end{verbatim} matvec product $(a, b, c)\!\!(d, e, f)$ \paragraph{Grassmann (1862)~\cite{Grassmann1862} - Ausdehnungslehre II.} Writes inner product as $[A | B]$, mentions $[A \times B]$ as an alternative notation (\S 137, p93 English). The outer (tensor) product is introduced without a name (Remark after \S 51) \begin{quote} ,,Ein Produkt, in welchern die Faktoren $a, b, \cdots$ irgend wie enthalten find, werde ich[...] mit $P_{a,b,...}$ bezeichnen`` \cite[p. 24, \S 43]{Grassmann1862} ``A product in which the factors a, b, ... are included in any way I will[...] denote by $P_{a,b,...}$''~\cite[p. 22, \S 43]{Grassmann2000} \end{quote} Later, the same quantity is referred to informally as ,,ein beliebiges Produkt $P_{a_1, a_2, ..., a_n}$``~\cite[\S 353]{Grassmann1862} (``an arbitrary product''~\cite[p. 196, \S 353]{Grassmann2000}) Also introduced the combinatorial product (Ch. 3), which we recognize today as the determinant. \paragraph{B. Peirce (1873)~\cite{Peirce1873} and C. S. Peirce (1874)~\cite{Peirce1874}} Developed the notion of matrix unit, which he called ``elementary relative'' in \cite[p.359]{Peirce1873}. B. Peirce (1874)~\cite{Peirce1874} explains that these units, which he called ``vids'', form the basis of a linear algebra. This paper also appears to be the earliest use of the phrase ``linear algebra'' (at least, in English). In 1883~\cite{Peirce1883} C. S. recognizes the significance for the algebra of matrices, called then by Clifford ``quadrics''. \paragraph{Frobenius (1878) - Ueber lineare Substitutionen und bilineare Formen} May have invented the term ``bilinear form''. \paragraph{Clifford (1878)~\cite{Clifford1878}} Clifford’s associative geometric product ŒClifford 1878 of two vectors simply adds the (symmetric) inner product to the (antisymmetric) outer product of Grassmann, - does it mean that he used the term also? \paragraph{Weierstrass (1884)~\cite{Weierstrass1884}} Publishes the notion of defining formal linear algebra through its structure constants. (He does not give the numbers a name.) \paragraph{Dedekind (1885)~\cite{Dedekind1885}} Extends Weierstrass to give the restriction on the structure constants so that the resulting algebra is associative. (He does not give the numbers a name either.) \paragraph{Peano (1888)~\cite{Peano1888}} Formalized axioms of vector space latent in Grassmann's work. May have also reintroduced the scalar product? Peano used [Peano 1887] for the scalar product, but called it “prodotto di due segmenti” (since in this book vectors were called ‘segmenti’). He used again later [Peano 1891a] and called it “prodotto (interno o geometrico).” \paragraph{Scheffers (1889)~\cite{Scheffers1889}} Formal linear algebra. Did he copy Weierstrass?? His paper has the same name. \paragraph{Molien (1892)} PhD thesis THEODOR MOHEN, "Ueber Systeme höherer complexer Zahlen," pp. 83-156. may have introduced the term ``Basis'' also relates hypercomplexes to matrices (148-156) Hawkins, "Hypercomplex Numbers, Lie Groups, and the Creation of Group Representation Theory," pp. 262-64. Gibbs and Heaviside (????) - may have introduced the scalar product? \paragraph{Prandtl (1903) and the German Vector commission} Recommended the notation of $\mathbf{a} \cdot \mathbf{b}$ a la Gibbs but called it the inner product à la Grassmann. \paragraph{Burali-Forti and Marcolongo (1907-1908) - Per l’unificazione delle notazioni vettoriali.} Proposed $\mathbf{a}\times\mathbf{b}$ for the scalar product and $\mathbf{a}\wedge\mathbf{b}$ for the vector product. \paragraph{MacDuffee (1933)~\cite{MacDuffee1933}} Starts with the abstract axioms of linear algebra and shows that the algebra may be represented by naturally by matrices and matrix multiplication. Also defines array as an ordered set with a known number of elements. Follows \cite{Scheffers1889}. \paragraph{Ritt (1950)} First use of the term ``structure constant'' ? \url{http://www.jstor.org/stable/1969444?seq=1#page_scan_tab_contents}

Grassmann's \textit{Ausdehnungslehre} of 1862\cite[Ch. 2]{Grassmann1862} introduces describes general structures to form products of two or more vectors. In modern language, if two vectors are expressed in some basis \begin{aligned} \begin{align} u & = \sum_i c_i e_i \\ v & = \sum_i d_i e_i \\ \end{aligned} \end{align} then any vector product operation $\circ$ is fully defined if the result of the operation $\circ$ on the basis vectors $e_i$ is known, since \[ u \circ v = \sum_{ij} c_i d_i (e_i \circ e_j) = \sum_{ij} c_i d_i G_{ij}

(b a^T) p = (a\cdot p) b, \] transcribing vectors into lower case letters in line with Householder's convention. In other words, Grassmann's open product is what we would call today the outer product, where ``open'' refers to the presence of the empty parenthesis denoting an ``opening''. Gibbs recognized the open product as a matrix in Multiple Algebra, Collected Works vol 2, p 94, but it is specifically a rank 1 matrix. (\textbf{TODO} Possibly the notion of rank did not exist then...?) In Gibbs's lecture notes of 1884, Sec. 107, p. 53 of Collected Works v2, he names the result of the indeterminate product of two vectors (in three dimensions) a dyad, and the linear combination of three dyads a dyadic, or what we would call today a 3x3 matrix. c.f. published version in Wilson1901.

and has the properties \begin{align} (A^T)^T & = A \\ (A + B)^T & = A^T + B^T \\ (\alpha A)^T & = \alpha A^T \text{ \textrm{ for all real numbers } \alpha \\ (A B)^T & = B^T A^T \end{align} Analogous definitions and properties for the $A^*$, the adjoint of $A$ (for operators over unitary space $\mathbb C^n$), appear on p. 266.

``If in an $n$-dimensional space a basis $\mathbf e_1, \mathbf e_2, \dots, \mathbf e_n$ has been chosen, then to every vector $\mathbf x$ there corresponds uniquely the column $x = (x_1, x_2, \dots, \mathbf x_n)$ where $x_1, x_2, \dots, \mathbf x_n$ are the coordinates of $\mathbf x$ in the given basis. Thus, the choosing of a basis establishes a one-to-one correspondence between the vectors of an arbitrary $n$-dimensional vector space $\mathbf R$ and the vectors of the $n$-dimensional number space $\mathbb F^n$... This means that to within isomorphism there exists only one $n$-dimensional vector space of a given number field.'' The fuss over the abstractions of vector space may seem fussy, but in fact it the definition of matrix multiplication arises naturally from the composition of linear operators, and is correct independent of basis. The notion of basis-independent properties is what is often neglected in computer representations, as is the notion of ``up to isomorphism'' as described by Gantmacher.