Earliest mention of permutation matrices, or equivalent? More generally, matrices for arbitrary functions between finite sets?

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

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"

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 reguläre Darstellung von $$\mathfrak{R}$$, bei der $$\mathfrak{R}$$ selbst Darstellungsmodul ist, eine Darstellung $$h$$-ten Grades von $$\mathfrak{g}$$, die man ebenfalls die regulä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.

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

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.

• I said I would be surprised if it was after Schur, not that I had seen it in Schur :-) Commented Jul 19, 2023 at 22:33
• @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. Commented Jul 20, 2023 at 3:19
• 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 ! Commented Jul 20, 2023 at 11:52
• 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/… Commented Jul 21, 2023 at 7:33
• probably as early as the concept of a regular representation of a group appeared. Frobenius, perhaps? Commented Jul 21, 2023 at 9:11

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.