6
$\begingroup$

Permutation matrices I assume have a long history, and would be surprised if they were first considered only long after the work of Shur just after 1900, on the representation theory of $S_n$.

Question 1 When were they first considered?

One can however assign a matrix to an arbitrary endomorphism of a finite set (with a given ordering): just the entries will be non-negative integers bounded above by the size of the set. More generally, one can assign a matrix to an arbitrary function between (ordered) finite sets.

Question 2 When was the first time someone thought of assigning a non-square matrix to a function of finite sets in an analogous way?

If one can think of a space of functions on a finite set, then the idea presumably comes rather quickly, but the earliest I've seen of this—the free vector space on a set being the set of functions of finite support—was an unpublished draft written by Ehresmann for Bourbaki dated somewhere between 1936 and 1940.


To give some upper and lower bounds for question 1, this is what I've found so far:

In the 1938 text The Theory Of Group Representations by Francis D. Murnaghan we have on page 17 a very brief introduction

enter image description here

and in

  • F. D. Murnaghan, On the Representations of the Symmetric Group, American Journal of Mathematics, Vol. 59, No. 3 (Jul., 1937), pp. 437–488 https://doi.org/10.2307/2371574

we have mention of permutation matrices without even defining what they are. I should mention that in Birkhoff and MacLane's 1941 A Survey of Modern Algebra permutation matrices are also mentioned (see eg page 227). So at least in the US mathematical community in the late 1930s, it seems that it was probably well-known. Possibly this was helped by Wedderburn's 1934 Lectures on Matrices, published by the AMS, where on page 33 we have the discussion of "elementary transformations"

enter image description here

in particular:

Since any permutation can be effected by a succession of transpositions, the corresponding transformation in the rows (columns) of a matrix can be produced by a succession of transformations of Type II.

and a formula for a general permutation matrix in the footnote. Wedderburn states in the introduction

This book contains lectures on matrices given at Princeton University at various times since 1920.

Going to the German algebraic tradition, we find in van der Waerden's 1935 Gruppen von Linearen Transformationen, page 54

Insbesondere liefert die reguläre Darstellung von $\mathfrak{R}$, bei der $\mathfrak{R}$ selbst Darstellungsmodul ist, eine Darstellung $h$-ten Grades von $\mathfrak{g}$, die man ebenfalls die reguläre Darstellung nennt. Die Matrixelemente von $A(s)$ sind in diesem Fall $$ \alpha_{ik}(s) = \begin{cases}1 & \text{für } ss_k = s_i\\ 0 & \text{sonst.} \end{cases} $$

Here $\mathfrak{R}$ is the group-ring of the finite group $\mathfrak{g}$, the $s_k$ are group elements (the basis of $\mathfrak{R}$), and $s$ is a general element of $\mathfrak{g}$. So at the least, this is a permutation matrix, if not named as such.

EDIT: I can now go back to 1925:

who mention "die Permutationsmatrix" associated to a permutation, on page 865:

Wir führen diesen Beweis, indem wir die Operation des Permutierens dureh Multiplikation mit einer geeigneten Matrix ersetzen.
Eine Permutation schreiben wir $$ \left(\begin{array}\ 0 &1 & 2 & 3&\ldots \\ k_0&k_1&k_2&k_3&\ldots\end{array}\right) = \left(\begin{array}\ n \\ n_n\end{array}\right). $$ Dieser ordnen wir die Permutationsmatrix $$ \mathbf{p} = \left(p(nm)\right),\quad p(nm)=\begin{cases}1&\text{für }m=k_n\\ 0 & \text{sonst}\end{cases} $$ zu.


EDIT 2: Schur in 1911 (Über die Darstellung der symmetrischen und der alternierenden Gruppe durch gebrochene lineare Substitutionen, https://eudml.org/doc/149348) gives a representation of $A_7$ (called here $\mathfrak{A}_7$) where the matrices (or "coefficient matrices" associated to generators) $Q_4$ and $Q_5$ are permutation matrices, though he doesn't single them out or name them as anything special.

Schur 1911 describing the relations between the matrices Qi

table of linear expressions for action of the matrices Qi on the basis vectors


On the other end of the timeline, I find in Burnside's Theory of groups of finite order, the second edition of 1911 which contains material on representations of groups "as groups of linear substitutions", on page 245:

The permutations of $n$ symbols that have been already considered are a very special case of linear substitutions.

without further fanfare. Linear substitutions are described as

...operation[s] performed on a set of $n$ symbols and leading to a new set of $n$ symbols

where the new symbols are linear functions of the old symbols (i.e. this is essentially, in modern terms, talking about mapping a basis to an new basis).

Additionally, in Bôcher's 1907 Introduction to higher algebra, page 276, the elementary matrices corresponding to switching rows are defined, but not a general permutation matrix as in Wedderburn's Lectures. Wedderburn attributes the idea of elementary transformations to Grassmann in 1862, in any case, so this aspect is far from new.

For question 2, the closest I've found is in

enter image description here enter image description here

from which it is conceivable one could consider the matrix $P$ associated to an induced injection between permutation groups arising from an injective function of sets, but this mere speculation on my part.

Similarly, one finds in

the weaker result (i.e. not a map between representations, just giving a canonical form for an arbitrary linear map):

b) Ist $P$ eine Matrix mit $m$ Zeilen und $n$ Spalten, deren Rang gleich $r$ ist, so lassen sich zwei Matrizen $A$ und $B$ der Grade $m$ und $n$ von nicht verschwindenden Determinanten bestimmen, so daß in der Matrix $APB = (q_{\alpha \beta})$ die $r$ Koeffizienten $q_{11}, q_{22},\cdots, q_{rr}$ gleich $1$, die übrigen Koeffizienten gleich $0$ sind.

Der zuletst angeführte Satz ist identisch mit dem bekannten Theorem, welches besagt, daß eine bilineare Form $f = \sum_{\alpha =1}^m\sum_{\beta =1}^np_{\alpha\beta}x_\alpha y_\beta$ vom Range $r$ sich auf die Gestalt $f = u_1v_1+u_2v_2+\cdots+u_rv_r$ bringen läßt, wo $u_1,u_2,\cdots,u_r$ und $v_1,v_2,\cdots,v_r$ linear unabhängige lineare homogene Funktionen der $m$ Variabeln $x_\alpha$ und der $n$ Variabeln $y_\beta$ bedeuten.

$\endgroup$
16
  • $\begingroup$ I said I would be surprised if it was after Schur, not that I had seen it in Schur :-) $\endgroup$ Jul 19 at 22:33
  • $\begingroup$ @njuffa no worries, and thanks for the advice. I can find the phrase "permutation matrix" in a 1938 book "The Theory Of Group Representations" by Murnaghan, which indicates to me it would have been well-established by then. He already used the name in a paper "On the Representations of the Symmetric Group" in the previous year, anyway. In looking at van der Waerden's 1935 book "Gruppen von Linearen Transformationen", he gives the regular representation ("reguläre Darstellung") of a finite group as a permutation matrix, though doesn't call it one. $\endgroup$ Jul 20 at 3:19
  • $\begingroup$ I will edit to include the above information and a couple of other things I've found. Thanks for pushing me to improve the question @njuffa ! $\endgroup$ Jul 20 at 11:52
  • 1
    $\begingroup$ You can narrow the upper bound for "permutation matrix" to 1930: see Atoms, Molecules and Quanta by Harold Urey at page 583-4, archive.org/details/dli.ernet.15949/page/583/mode/… $\endgroup$
    – user6530
    Jul 21 at 7:33
  • $\begingroup$ probably as early as the concept of a regular representation of a group appeared. Frobenius, perhaps? $\endgroup$ Jul 21 at 9:11

1 Answer 1

1
$\begingroup$

Study of circulants goes way back to at least 1842 (Catalan) - they are linear combinations of cyclic permutation matrices. A very nice article by Keith Conrad has this and many other relevant references.

Although I think as soon as one realises that the determinant of a $n\times n$-matrix $A$ can be written as a sum over $S_n$ of determinants of permutation matrices (with entries weighted by the entries of $A$), one gets permutation matrices, so it's even much earlier than 1842.

$\endgroup$
2
  • 2
    $\begingroup$ The Catalan's article is here: orbi.uliege.be/bitstream/2268/193536/1/Catalan036.pdf clearly there is no reference to permutation matrices for the simple reason that the term was introduced by Sylvester in 1850, and Frobenius started using it only in 1894. In any case, I suggest reading sciencedirect.com/science/article/pii/0315086075901445 $\endgroup$
    – user6530
    Jul 21 at 11:33
  • $\begingroup$ @user6530 thanks for that reference. I'm trying also to avoid, in applying the results here to my ultimate aim, a second-order version: it was known at that time by some people, therefore everyone at that time must have known it! $\endgroup$ Jul 21 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.