Editing Permutation matrix (section)

==Linear-algebraic properties==

Just as each permutation is associated with two permutation matrices, each permutation matrix is associated with two permutations, as we can see by relabeling the example in the big square above starting with the matrix ''P'' at the upper right:
:<math>\begin{matrix} 
\rho_P\colon\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}
& \longleftrightarrow &
P\colon\begin{pmatrix}
0&0&1&0\\
0&1&0&0\\
0&0&0&1\\
1&0&0&0\end{pmatrix}\\[5pt]
\Big\updownarrow && \Big\updownarrow\\[5pt]
P^{-1}\colon\begin{pmatrix}
0&0&0&1\\
0&1&0&0\\
1&0&0&0\\
0&0&1&0\end{pmatrix}
& \longleftrightarrow &
\kappa_P\colon\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}\end{matrix}</math>
So we are here denoting the inverse of ''C'' as <math>\kappa</math> and the inverse of ''R'' as <math>\rho</math>.  We can then compute the linear-algebraic properties of ''P'' from some combinatorial properties that are shared by the two permutations <math>\kappa_P</math> and <math>\rho_P=\kappa_P^{-1}</math>.

A point is [[Fixed point (mathematics)|fixed]] by <math>\kappa_P</math> just when it is fixed by <math>\rho_P</math>, and the [[Trace (linear algebra)|trace]] of ''P'' is the number of such shared fixed points.<ref name="Artin Algebra" />{{rp|page=322}}  If the integer ''k'' is one of them, then the [[standard basis]] vector {{math|'''''e'''''<sub>''k''</sub>}} is an [[eigenvector]] of ''P''.<ref name="Artin Algebra" />{{rp|page=118}}

To calculate the complex [[eigenvalue]]s of ''P'', write the permutation <math>\kappa_P</math> as a composition of [[cyclic permutation|disjoint cycles]], say <math>\kappa_P= c_{1}c_{2} \cdots c_{t}</math>.  (Permutations of disjoint subsets commute, so it doesn't matter here whether we are composing right-to-left or left-to-right.) For <math>1 \le i \le t</math>, let the length of the cycle <math>c_i</math> be <math>\ell_i</math>, and let <math>L_{i}</math> be the set of complex solutions of <math>x^{\ell_{i}}=1</math>, those solutions being the <math>\ell_i^{\,\text{th}}</math> [[root of unity|roots of unity]]. The [[multiset]] union of the <math>L_{i}</math> is then the multiset of eigenvalues of ''P''.  Since writing <math>\rho_P</math> as a product of cycles would give the same number of cycles of the same lengths, analyzing <math>\rho_p</math> would give the same result.  The [[Eigenvalues and eigenvectors#Eigenvalues and eigenvectors of matrices|multiplicity]] of any eigenvalue ''v'' is the number of ''i'' for which <math>L_i</math> contains ''v''.<ref name=J_Najnudel2010_4>{{harvnb|Najnudel|Nikeghbali|2013|p=4}}</ref> (Since any permutation matrix is [[Normal matrices|normal]] and any normal matrix is [[diagonalizable matrix|diagonalizable]] over the complex numbers,<ref name="Artin Algebra" />{{rp|page=259}} the algebraic and geometric multiplicities of an eigenvalue ''v'' are the same.)
	
From [[group theory]] we know that any permutation may be written as a composition of [[transposition (mathematics)|transposition]]s. Therefore, any permutation matrix factors as a product of row-switching [[elementary matrix|elementary matrices]], each of which has [[determinant]] &minus;1. Thus, the determinant of the permutation matrix ''P'' is the [[parity of a permutation|sign]] of the permutation <math>\kappa_P</math>, which is also the sign of <math>\rho_P</math>.