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 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:
- Born, M., Jordan, P. Zur Quantenmechanik. Z. Physik 34, 858–888 (1925). https://doi.org/10.1007/BF01328531,
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
- I. Schur, Beiträge zur Theorie der Gruppen linearer homogener Substitutionen, Trans. Amer. Math. Soc. 10 (1909), 159-175, https://doi.org/10.1090/S0002-9947-1909-1500832-1
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
- I. Schur, Neue Begrüdung der Theorie der Gruppencharaktere, Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften zu Berlin (1905) pp 406–432 https://archive.org/details/bub_gb_KwUoAAAAYAAJ/page/406/mode/1up
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.
