In search of the origins of matrix multiplication
Jerzy Respondek/
1 Origins of matrices and determinants
In this note we present the history of the development of matrices and determinants. To the best of our knowledge, we found the first general definition of matrix multiplication. This is particularly important given the wealth of algorithms currently available that perform fast matrix multiplication.
Additionally, we provide a broad historical overview of nearly one hundred books on the subject written in eight languages.
The concept of a two-dimensional mathematical matrix is a fundamental one in science and engineering. As documented, for example, in the monograph by Yong, Se [92], the concept of Gauss elimination, and thus an early version of matrices, was already known in ancient times. Section 7.7, pages 145–154, describes the process of transforming the source system matrix into a triangular form in order to solve a system of three linear equations with three unknowns.
It is difficult to decide whether to begin a historical overview with determinants or matrices. On the one hand, matrices seem to play a greater role today, with determinants playing a supporting role. On the other hand, however, at a time when matrices were just being defined (1850-51), and when the first articles systematizing their fundamental properties appeared (1855, 57), it was around this time that the first comprehensive and quite extensive monographs on determinants appeared (1851).
Maybe, it is surprising that determinants are a much older concept than matrices. According to the 1890 monograph by Muir [49], they were invented as early as 1693 by Leibnitz, albeit in a different notation. For a comprehensive study of the history of determinants, see the classic and still valuable monographs by Muir [49]-[51].
2 An outline of the history of determinants
This overview begins with the first book, published in 1851, and ends roughly with World War II. As we will see, by that time books had been published in at least eight languages, covering mathematical and educational topics and presenting applications not only in other branches of mathematics, but also in engineering. Interestingly, among them already are works from the 19th century on special matrices (in the form of determinants) and even historical studies.
Let us begin our review with English-language works. However, we made this selection based on the language in which the first book was published. The table lists the first edition of each item. We applied this rule to not only English books, and we reviewed (selected) later editions separately, if applicable.
Table 1. English historical books on determinants
It is worth noting here that some books indicate in their titles that they concern applications – Dodgson (1867) [17] and Few (1922) [26] . The latter even applies to engineering applications.
We also have the first books that are intended to be textbooks – they are Hanus (1886) [34], Taylor (1896) [76] and Thomson (1882) [77]. It’s worthy to note that one of them, by Thomson, in its very tile is intended not even for use at the higher education level, but for use in schools.
As can be seen, Muir not only published a very comprehensive study on the history of determinants, but also his own, single-authored work, and was also the co-author of extensive monographs in this area.
On page 51, Scott (1880) [69] provides a formula for computing the determinant of a block-diagonal matrix. In Chapter 4, entitled “Multiplication of Determinants” Scott unintentionally provides a definition of matrix multiplication. In Sect. 3 Spottiswoode did this in 1851. We will discuss this topic further later in the article.
Scott published the second edition of his book in 1904 [70]. Weld’s book saw its fourth edition in 1906 [90].
The second language in which the book on determinants was published was Italian. The table below presents the titles that appeared.
Table 2.
As you can see from the title, four out of five of them also discuss applications. Brioschi in 1856 [8] published French version of His book. Pascal also published the German version in 1900 [57].
The next book was published in German, in which we found the most titles.
Table 3. German historical books on determinants
Baltzer published the French edition in 1861 [5]. Günther published the second edition in 1877 [33], Prang in 1908 [62], Fischer in 1921 [28], and Netto in 1925 [55]. Items Dolp [18] and Reidt [63] are clearly didactic in nature.
A similar tally for French books is presented in Table 4.
Table 4. French historical books on determinants
The fourth edition of the Mansion’s book in French was published in 1883 [46].
There are editions in German, the first of which was published in 1878 [43], followed by a second edition in 1899 [44].
The latest compilation of numerous historical books can be made for the Spanish language. It is just below.
Table 5. Spanish historical books on determinants
The third edition of Villafañe (1891) was published in 1897 [83]. Prado (1891) had subsequent editions in 1895 and 1902. It is worth noting that José Echegaray won the Nobel Prize in Literature in 1904.
Table 6 below shows the positions on the determinants in the remaining languages.
Table 6. Dutch, Russian, and Ukrainian historical books on determinants
The fourth edition of Vinogradov’s work was published in 1935 [85].
As can be seen from Tables 1-6, the titles in each language accurately reflect the high level of understanding of the determinants in that era.
Also it is definitely worth noting here that the first historical study of determinants, authored by František Josef Studnička [72], dates back to 1876, and therefore has historical value in itself. It was written in German, but published in Prague. It was published 14 years earlier than the first volume of Muir’s History of Determinants, which was published in 1890.
3 An outline of the history of matrices
Let’s now move on to the matrix. The concept of a matrix was first introduced by Sylvester in article [74] from 1850, on page 369, and again by Sylvester in article [75] from 1851, on page 302. Roughly speaking, Sylvester describes it as a creation, in general not necessarily square, from which we can pick a certain number of determinants. In other words, Sylvester defined the matrix as a subordinate concept to the determinants. In addition to defining the concept of a matrix in the first of these two articles, Sylvester devotes most of his attention to analyzing how many minors can be obtained from a given matrix, while in the second article he considers matrices in the context of quadratic forms.
Many authors consider Cayley’s 1857 article [12] to be the first comprehensive work devoted specifically to the topic of matrices. The 21-page text discusses 58 matrix operations and their properties.
However, the author of this study successfully found an older article by the same author from 1855 [11]. It presents the basic concepts and applications of matrices in a quite mature way. He applies them to the notation of a system of linear equations, presents its solution, and simultaneously defines the inverse of a matrix. In addition, he indirectly defines the operation of matrix multiplication through the product of determinants. Finally, he applies them to the notation of what he calls quadratic functions, which today we would call quadratic forms.
The author of this analysis also came across a lesser-known work by Caley from 1866 [13].
In it, he presents another 23 properties of matrices, directly pointing out that they were not included in his most known article from 1857 (“It is not in the Memoir on Matrices explicitly remarked.”).
Below is a chronological overview of books which, with the exception of the first, are devoted to matrices, as indicated by their titles.
• 1907 – The first book in which matrices play an important role is generally considered to be Bocher, Duval [6]. Although the concept of a matrix (or determinant) does not appear in the title of the book, but only in the titles of chapters II, V, VI, and XX, it plays an important role throughout the book. Interestingly, this is probably the only book on matrices whose authors do not use the standard notation of denoting matrices with capital letters.
• 1913, 1918, 1925 – Cullis [15] is an extensive, three-volume monograph on matrices and determinants that is known as the first book devoted exclusively to them.
• 1928 – Turnbull [79]. The second edition was published in 1945.
• 1931 – Turnbull, Aitken [80]. The second edition of this book was published in 1944, and the third in 1961. This book remains a classic and widely used reference on canonical matrix forms.
• 1932 – This year saw the publication of the first book in German on the subject of matrices Schreier, Sperner [68]. In 1936, a Russian translation was published.
• 1933 – MacDuffee published the first edition of his book [20], which is still highly regarded and in use today. In 1956, the last [21], revised edition was published.
• 1934 – Wedderburn published his book [87], which is still frequently used as a source of knowledge on various fundamental aspects of matrix calculus. It is particularly valued for its comprehensive overview of articles on this topic from around the time the concept was defined (1853) to the time of publication. It covers over 660 items!
• 1938 – Frazer, Duncan, and Collar published a book [30] that is quite extensive, spanning over 400 pages. In addition to theoretical lectures, it also covers numerical methods related to matrices and discusses a wide range of applications in detail.
• 1939 – Aitken published his book [1], the latest, ninth edition of which [2] is still used today alongside other contemporary monographs.
• 1941 – Ferrar published [25], and its second edition in 1957.
• This is the second German-language book [53] in our list by F. Neiss. In 1975, the eighth edition was published, co-authored with H. Liermann.
• 1943 – MacDuffee published his second book [22].
4 An outline of the history of matrix multiplication
Now let us go to the matrix multiplication. The most frequently cited source here is Cayley’s 1857 article, mentioned above. Indeed, in point 11 of Cayley’s article [32], on pages 20–21, a definition of matrix multiplication is given (in notation very different from the modern one). However, he provides a definition of this operation only for the specific case of low dimensionality 3×3. We had to wait until 1907 for a monograph defining this operation in general terms, when Bocher undertook this task in section VI.22 of his book on linear algebra [6]. The first book devoted exclusively to matrices, defining their multiplication in the general case in §42, is Cullis, Vol. I, 1913 [15].
Meanwhile, in the early years of development, matrix multiplication was defined (in the general case, for any dimensionality of the multiplied matrices) earlier indirectly as an auxiliary tool for determinants. A monograph by Spottiswoode [71] makes it in 1851. It is in §V:”On the Products and Powers of Determinants”. To the best of the author’s knowledge, this is the first fully general definition of matrix multiplication in history. It is worth noting that this is the same year in which the concept of the matrix was first defined by Sylvester. Other early books devoted entirely to determinants, which indirectly define matrix multiplication in the general case, include: Baltzer (1857) [4], §6.4:”Das Product von beliebig vielen Determinanten” and Scott (1880) [69], Section 3 on pages 46-47, the defining formula is presented in the context of the formula for the determinant of a product of matrices. It is worth noting that the former was published in the same year as Caley’s most often cited study [32]. The aforementioned historical study by Studnicka [72] in §8 noted that Gauss indirectly used matrix multiplication in his 1802 work for the 3×3-dimensional case.
5 Conclusion – why matrix multiplication is so important
One way to speed up matrix operations is to use fast matrix multiplication algorithms.
Their advantage is their generality, i.e. their input parameters are matrices with arbitrary allowed values for each entry. Today, we know universal algorithms for matrix multiplication that is as efficient as slightly above O(n^2.37). The most known one is the famous Coppersmith, Winograd [14] paper.
References
[01] A.C. Aitken, Determinants and Matrices, Oliver and Boyd, Edinburgh, 1939.[02] A.C. Aitken, Determinants and Matrices, Ninth Edition, Interscience Publishers, Inc. New York, 1956.
[03] V. Bacas, Teoría elemental de las determinantes y sus aplicaciones al álgebra y a la geometría, Imprenta de la Viuda e Hijos de J.E. del Amo, Madrid, 1883.
[04] R. Baltzer, Theorie und Anwendung der Determinanten mit Beziehung auf die Originalquellen, S. Hirzel, Leipzig, 1857.
[05] R. Baltzer, Théorie et applications des déterminants : avec l’indication des sources originales, Mallet-Bachelier, Paris, 1861.
[06] M. Bocher, E.P.R. Duval, Introduction to Higher Algebra, The MacMillan Company, New York, 1907.
[07] F. Brioschi, La Teorica dei Determinanti e le sue Principali Applicazioni, Tipografia Degli Eredi Bizzoni, Pavia, 1854.
[08] F. Brioschi, Théorie des déterminants et leurs principales applications, Mallet-Bachelier, Paris, 1856.
[09] W.S. Burnside, A.W. Panton, An Introduction to Determinants: Being a Chapter from The Theory of Equations, Hodges, Figgis & Co., Dublin, 1899.
[10] F. Caldarera, Trattato dei determinanti, Stabilimento Tipografico Virzì, Palermo, 1913.
[11] A. Cayley, Remarques sur la notation des fonctions algébriques, Journal für die reine und angewandte Mathematik, 50 (1855) 282–285.
[12] A. Cayley, A Memoir on the Theory of Matrices, Philosophical Transactions of the Royal Society of London 148 (1857) 17-37.
[13] A. Cayley, „A Supplementary Memoir on the Theory of Matrices, Philosophical Transactions of the Royal Society of London, 156 (1866) 25–35.
[14] D. Coppersmith, S. Winograd, Matrix multiplication via Arithmetic Progressions, J. Symbolic Computation 9 (1990) 251-280.
[15] C.E. Cullis, Matrices and Determinoids, Vol. 1-3, Cambridge University Press, Cambridge, UK, 1913, 1918, 1925.
[16] F.J.K. Diekmann, Einleitung in die Lehre von den Determinanten und ihrer Anwendung, G.D. Baedeker, Essen, 1876.
[17] Ch.L. Dodgson, An Elementary Treatise on Determinants, with their application to simultaneous linear equations and algebraical geometry, Macmillan and Co., London, 1867.
[18] H. Dolp, Die Determinanten, elementar behandelt: Ein Lehrbuch für Schulen und zum Selbstunterricht, Verlag von L. Saunier’s Buchhandlung, Darmstadt, 1874.
[19] G. Dostor, Éléments de la théorie des déterminants, Gauthier-Villars, Paris, 1877.
[20] C.C. Mac Duffee, The Theory of Matrices, Springer Verlag, Berlin, Germany, 1933.
[21] C.C. Mac Duffee, The Theory of Matrices, Corrected Reprint of First Edition, Chelsea Publishing Company, New York, 1956.
[22] C.C. Mac Duffee, Vectors and Matrices, The Mathematical Association of America, 1943.
[23] J. Echegaray, Memoria sobre la teoría de las determinantes, Imprenta de Los Conocimientos Útiles, Madrid, 1868.
[24] J. Echegaray, Aplicación de la teoría de las determinantes á la geometría de tres dimensiones, Imprenta de la Revista de Legislación, Madrid, 1869.
[25] W.L. Ferrar, Algebra. A textbook of determinants matrices and algebraic forms, Oxford University Press, London, 1941.
[26] H.P. Few, Elementary Determinants for Electrical Engineers, S. Rentell & Co., Ltd., London, 1922.
[27] P.B. Fischer, Determinanten, G.J. Göschensche Verlagshandlung, Leipzig, 1908.
[28] P.B. Fischer, Determinanten, Zweite, verbesserte Auflage, G.J. Göschensche Verlagshandlung, Leipzig, 1921.
[29] D. Fontebasso, I primi elementi della teoria dei determinanti e loro applicazioni all’algebra ed alla geometria proposti agli alunni degli istituti tecnici, Tipografia di G. Longo, Treviso, Italy, 1873.
[30] R.A. Frazer, W.J. Duncan, A.R. Collar, Elementary matrices and some applications to dynamics and differential equations, Cambridge University Press, Cambridge, UK, 1938.
[31] P. Gilbert, Sur une propriété des déterminants fonctionnels et son application au développement des fonctions implicites, F. Hayez, Imprimeur de l’Académie Royale, F. Hayez, Imprimeur de l’Académie Royale, 1869.
[32] S. Günther, Lehrbuch der Determinanten-Theorie für Studirende, E. Besold Verlag, Erlangen, 1875.
[33] S. Günther, Lehrbuch der Determinanten-Theorie für Studirende, Auflage 2, E. Besold Verlag, Erlangen, 1877.
[34] P.H. Hanus, An elementary treatise on the theory of determinants: A text-book for colleges, Ginn & Company, Boston, 1886.
[35] E.R. Heineman, Generalized Vandermonde Determinants, Trans. Amer. Math. Soc. 31 (1929) 464-476.
[36] L.O. Hesse, Die Determinanten elementar behandelt, B.G. Teubner, Leipzig, 1872.
[37] В. Каган, Основания теории определителей, Государственное издательство Украины, Odessa, 1922.
[38] L.V. Kantorovich, V.I. Krylov, Методы приближенного решения уравнений в частных производных, Объединение научно-технических издательств, Moscow, Russia, 1936.
[39] H. von Koch., Sur les déterminants infinis et les équations différentielles linéaires, Stockholm, Imprimiere Centrale, 1892.
[40] G. Kowalewski, Einführung in die Determinantentheorie einschließlich der unendlichen und der Fredholmschen Determinanten, Verlag von Veit & Comp., Leipzig, 1909.
[41] L. Kronecker, Vorlesungen über die Theorie der Determinanten, B.G. Teubner Verlag, Leipzig, 1903.
[42] L. Leboulleux, Traité élémentaire des déterminants avec des applications à l’algèbre et à la géométrie, Gauthier-Villars/Librairie Ch. Poussielgue, Paris, 1884.
[43] P. Mansion, Elemente der Theorie der Determinanten mit vielen Übungsaufgaben, Verlag von B.G. Teubner, Leipzig, 1878.
[44] P. Mansion, Elemente der Theorie der Determinanten mit vielen Übungsaufgaben, Zweite, verbesserte Auflage, Verlag von B.G. Teubner, Leipzig, 1899.
[45] P. Mansion, Éléments de la théorie des déterminants, avec de nombreux exercices, Gand, Imprimerie G. Dubrulle., 1875.
[46] P. Mansion, Éléments de la théorie des déterminants, avec de nombreux exercices, Quatrieme Edition, Adolphe Hoste (Gand)/Gauthier-Villars (Paris), Gand (Belgique) et Paris (France), 1883.
[47] G.A. Miller, Determinants: An Introduction to the Study of, with Examples and Applications, D. Van Nostrand Company, New York, 1892.
[48] T. Muir, A treatise on the theory of determinants, MacMillan and Co., London, UK, 1882.
[49] T. Muir, The Theory of Determinants in the Historical Order of Its Development. Part I. Determinants in General. Leibnitz (1693) to Cayley (1841), MacMillan and Co., London, UK, 1890.
[50] T. Muir, The theory of Determinants in the Historical Order of Development. Volumes Two to Four. The Periods 1841 to 1860, 1861 to 1880, 1880 to 1900, Dover Publications, Inc., New York, USA, 1911, 1920, 1923.
[51] T. Muir, Contributions to the History of Determinants. 1900-1920, Blackie & Son Limited, London and Glasgow, UK, 1930.
[52] T. Muir, W.H. Metzler, Theory of Determinants, Longmans, Green and Co., Bombay, Calcutta, Madras, India, 1933.
[53] F. Neiss, Determinanten und Matrizen, Springer-Verlag Berlin Heidelberg Gmbh, 1941.
[54] E. Netto, Die Determinanten, B.G. Teubner Verlag, Leipzig und Berlin, 1910.
[55] E. Netto, Die Determinanten, Zweite, verbesserte Auflage, B.G. Teubner Verlag, Leipzig und Berlin, 1925.
[56] E. Pascal, I determinanti: Teoria ed applicazioni, Ulrico Hoepli, Milano, 1897.
[57] E. Pascal, Die Determinanten: Eine Darstellung ihrer Theorie und Anwendungen mit Rücksicht auf die neueren Forschungen, B.G. Teubner, Leipzig, 1900.
[58] W.G. Peck, Elementary Treatise on Determinants, A.S. Barnes & Company, New York and Chicago, 1887.
[59] J. Peters, Determinanten, Verlag von Robert Noske, Borna-Leipzig, 1925.
[60] G. Prado, Elementos de la teoría de los determinantes y sus aplicaciones a la resolución de los sistemas de ecuaciones lineales, Establecimiento Tipográfico de “La Derecha”, Madrid, 1891.
[61] F. Prang, Einführung in die Theorie und den Gebrauch der Determinanten, Leonhard Simion Verlag, Berlin, 1899.
[62] F. Prang, Determinanten, G.P. Aderholz Verlag, Breslau, 1908.
[63] F. Reidt, Vorschule der Theorie der Determinanten: Mit Anwendungen auf die Elementar-Mathematik; für Gymnasien und Realschulen bearbeitet, G.W. Körner’s Verlag, Leipzig, 1874.
[64] M. Reiss, Beiträge zur Theorie der Determinanten, B.G. Teubner, Leipzig, 1867.
[65] E.D. Roe Jr., Die Entwickelung der Sylvester’schen Determinante nach Normal-Formen, Druck von B. G. Teubner, Leipzig, 1898.
[66] J.B. Scarborough, Numerical Mathematical Analysis, George Banta Publishing Company, Menasha, Wisconsin, USA, 1930.
[67] W. Schrader, Beiträge zur Theorie der Determinanten, Verlag von G.W. Körner, Halle, 1887.
[68] O. Schreier, E. Sperner, Vorlesungen über Matrizen, Hamburger Mathematische Einzelschriften, Leipzig, Berlin, 1932 (Russian edition: Moscow, 1936).
[69] R.F. Scott, Theory of Determinants, Cambridge University Press, Cambridge, UK, 1880.
[70] R.F. Scott, Theory of Determinants, 2nd edition, Cambridge University Press, Cambridge, UK, 1904.
[71] W. Spottiswoode, Elementary theorems relating to determinants, Spottiswoodes & Shaw, London, 1851.
[72] F.J. Studnička, A.L. Cauchy als formaler Begründer der Determinanten-Theorie. Eine literarisch-historische Studie, Gedruckt bei der Königlich Böhmischen Gesellschaft der Wissenschaften, Prag, 1876.
[73] S. Suárez, J. Rodríguez, A. Gascó, Lecciones de combinatoria con las determinantes y sus principales aplicaciones, Imprenta de la Viuda e Hijos de J. E. del Amo, Madrid, 1882.
[74] J.J. Sylvester, Additions to the articles in the September number of this journal, “On a new class of theorems,” and on Pascal’s theorem, Phil. Mag. 3 (37) (1850) 363-370.
[75] J.J. Sylvester, On the Relation between the Minor Determinants of Linearly Equivalent Quadratic Functions, Phil. Mag. 4 (1) (1851) 295-305.
[76] J.M. Taylor, Elements of Determinants: Designed for High Schools and the Lower Classes of Colleges and Universities, Ginn & Company, Boston and London, 1896.
[77] W. Thomson, An introduction to determinants, with numerous examples, for the use of schools and colleges, J. Thin, Edinburgh, Scotland, 1882.
[78] N. Trudi, Teoria de’ determinanti e loro applicazioni, Pellerano, Napoli, 1862.
[79] H.W. Turnbull, The theory of Determinants, Matrices and Invariants, Blackie & Son, London & Glasgow, UK, 1928.
[80] H.W. Turnbull, A.C. Aitken, An Introduction to the Theory of Canonical Matrices, London, Glasgow and Bombay: Blackie and Son, 1932.
[81] F. de P. Villafañe, Teoría de las determinantes, Imprenta de Jaime Jepús, Barcelona, 1888.
[82] F. de P. Villafañe, Elementos de las teorías combinatoria y de las determinantes con sus aplicaciones, Imprenta de Jaime Jepús, Barcelona, 1891.
[83] F. de P. Villafañe, Elementos de las teorías combinatoria y de las determinantes con sus aplicaciones, Tercera Edición, Imprenta de Jaime Jepús, Barcelona, 1897.
[84] С.П. Виноградов, Основания теории детерминантов, Книгоиздательство Студенческая Комиссия при Обществе Взаимопомощи Студентов Императорского Московского Технического Училища, Москва, 1915.
[85] С.П. Виноградов, Основания теории детерминантов, 5-е издание (исправленное и дополненное), Объединенное научно-техническое издательство), Главная редакция общетехнической литературы и номографии, Москва, Ленинград, 1935.
[86] G.W. Wageningen, De determinanten elementair behandeld, Gebroeders van der Post, Utrecht, Nederlands, 1871.
[87] J.H.M. Wedderburn, Lectures on Matrices. American Mathematical Society, Colloquium Publications, Providence, Rhode Island, USA, 1934.
[88] G. Weichold, Lehrbuch der Determinanten und deren Anwendungen (Teil 1: Die Theorie der Determinanten), Verlag von L. Ehlermann, Dresden/Leipzig, 1893.
[89] L.G. Weld, A Short Course in the Theory of Determinants, Macmillan and Co., New York and London, 1893.
[90] L.G. Weld, A Short Course in the Theory of Determinants, 4th edition, Macmillan and Co., New York and London, 1906.
[91] W.J. Wright, Tracts relating to the modern higher mathematics. Tract No. 1. Determinants, C.F. Hodgson & Son, London, 1875.
[92] L.L. Yong, A.T. Se, Fleeting Footsteps. Tracing the Conception of Arithmetic and Algebra in Ancient China, World Scientific Publishing, Singapore, 2004. ^1 Published in Belgium.
|| Go to the Math & Research main page
