Missing condition for permutation matrices in MatrixWorld-v1.4.2

[seblucie]

Thanks for this fantastic resource! One small issue in the MatrixWorld diagram:

MatrixWorld-v1.4.2 defines permutation matrices P as:

• Orthogonal matrices for which all $\lambda$ are roots of 1

This is necessary but not sufficient for P to be a permutation matrix. Two examples of matrices satisfying this property that are not permutation matrices:

• $Q = \begin{bmatrix} -1 \end{bmatrix}$ has eigenvalue $-1$
• $Q = \begin{bmatrix} 0 & 1 \end{bmatrix} \begin{bmatrix} - 1 & 0 \end{bmatrix}$, the example provided of an orthogonal matrix that is not a permutation matrix, has eigenvalues $\pm i$

This can be fixed by defining permutation matrices P as the intersection of:

• Orthogonal matrices for which all $\lambda$ are roots of 1, with
• Nonnegative matrices, i.e. matrices for which all elements are $\ge 0$

The equivalence follows from https://en.wikipedia.org/wiki/Nonnegative_matrix#Inversion: "The inverse of a non-negative matrix is usually not non-negative. The exception is the non-negative monomial matrices", where a monomial matrix is defined to have "the same nonzero pattern as a permutation matrix, i.e. there is exactly one nonzero entry in each row and each column." Hence an orthogonal nonnegative matrix must be a non-negative monomial matrix, and an orthogonal nonnegative matrix with all eigenvalues roots of unity must be a permutation matrix.

[kenjihiranabe]

Wow, thank you ! You are right. How about just saying "permutation of I(identity)", for a beginner-friendly notation?

[kenjihiranabe]

But $a_{ij} \ge 0$ would be a nice comment to add!

[kenjihiranabe]

Permutation matrix has only one 1 in each column and other elements are all 0 ! So $a_{ij} \ge 0$ is covered by one definition sentence -- "permutation of I(identity)".

[seblucie]

Hmm, adding nonnegative matrices to the diagram would be too messy, as they have partial overlap with almost all other matrix classes.

So I think you're right, describing permutation matrices as "Permutations of I (identity)" seems like the best option!

Other possibilities:

• "Permutes the rows/columns of I" - but we don't mention rows/columns elsewhere
• "Permutes coordinate basis vectors $P_\pi ei = e{\pi(i)}$" - might be OK, shows that permutation matrices are basis-dependent...

(Also note https://en.wikipedia.org/wiki/Permutation_matrix#Properties: "When viewed as matrices with real number entries, permutation matrices can be characterized as the orthogonal matrices whose entries are all non-negative." So we could drop the roots of unity condition if we mention non-negativity. But I think it's too complicated a definition, let's go with your one instead!)

[seblucie]

... alternately, if we want a basis-independent definition of permutation matrices, i.e. we want to ask which matrices have some basis under which they can be written as permutation matrices, these are precisely the "orthogonal matrices for which all $\lambda$ can be grouped into roots-of-unity cycles" - see Qiaochu Yuan's comments in https://math.stackexchange.com/questions/1994911/representing-unitary-matrices-as-permutations-in-some-basis 🤯

I.e. the original definition was almost right, we just need to add a cycles condition to rule out examples like $\begin{bmatrix} -1 \end{bmatrix}$ and $\begin{bmatrix} 0 & 1 \end{bmatrix} \begin{bmatrix} - 1 & 0 \end{bmatrix}$!

[kenjihiranabe]

you are so talented, seblucie! This is exactly what Prof.Strang and I were talking about!

[kenjihiranabe]

you maybe interested in this too. this is in this repository too. https://anagileway.com/2021/10/01/map-of-eigenvalues/

[seblucie]

Thanks! - but Professor Strang is a living legend, whereas I'm just good at looking stuff up.

I did have one further idea - we could define "cycles of eigenvalues" via the characteristic polynomial: $\displaystyle \det(\lambda I - P\pi) = \prod{i} (\lambda^{p_i} - 1)$, where $p_i = \textrm{lengths of cycles in }\pi$

(Hence e.g. $\operatorname{diag}(1, 1, 1, -1)$ and $\operatorname{diag}(1, 1, -1, -1)$ are orthogonally equivalent to permutation matrices, whereas $\operatorname{diag}(1, -1, -1, -1)$ is not.)

But I'm sure Prof. Strang will give you the right advice - I'll leave it to you to decide where to go from here...