Talk:Permutation matrix

Determinant of perm matrix

I have been told (as the answer to an exam question) that:

For an nxn matrix A, and nxn permutation matrix P:
det(A) = det(inv(P).A.P)

Anyone care to explain why?

--KarlOkeeffe

A permutation matrix is an orthogonal matrix, which has determinant 1 or -1, and the determinant of the inverse is the inverse of the determinant of the matrix. And 1/1=1 and 1/-1=-1, so det(inv(P).A.P) = det(inv(P)) * det(A) * det(P) = either 1 * det(A) * 1 or -1 * det(A) * -1 = det(A). Or something like that. Similar matrix may or may not be relevant, if the term exists. (Suppose it's probably called that in english as well as danish.) Κσυπ Cyp 10:17, 15 Oct 2003 (UTC)

More simply, permutation matrices are always invertible (since S_n is a group) and inv(P)AP is a similarity transformation, and the determinant is a similiarity invariant. Dysprosia 11:26, 8 Mar 2005 (UTC)

Constant line sums

I have added an entry on a possible generalization of permutation matrices. Perhaps someone can clear up the following points.

1. is there a name for my generalization of permutation matrices ?
2. how is my generalization related to the generalization on the page Generalized_permutation_matrix ?
3. what is the relation to double-stochastic matrices ?

MathMartin 17:13, 28 Jun 2004 (UTC)

See above for the name. Divide by c and you get a doubly stochastic matrix.Zaslav 11:16, 4 November 2006 (UTC)

Rows Or Columns?

The relation $P_{\pi }P_{\sigma }=P_{\pi \circ \sigma }$ contradicts

$P_{\pi }\mathbf {g} ={\begin{bmatrix}g_{\pi (1)}\\\vdots \\g_{\pi (n)}\end{bmatrix}}$

(The RHS gives a right action.) The reasonable solution seems to be to use columns instead of rows in the definition, cf. de:Permutationsmatrix.--gwaihir 22:58, 15 February 2006 (UTC)

Left and Right Prodruct

The product $PM$, permutes the rows of $M$. I corrected that in the text. Please check it.

It's correct.Zaslav 11:14, 4 November 2006 (UTC)

Incoherent section

The section "Solving for P" makes no sense. What are A and B? Certainly, not arbitrary matrices. I suggest this section be removed. If not, it must be completely rewritten so that the reader can tell what it is about. (I cannot.) Zaslav 11:13, 4 November 2006 (UTC)

I agree that something needs to be done to fix this. This section is misleading, since if you compute Q_B Q_A' you do not end up with P that conforms to the (0,1)-definition. (June 2008)

I am guessing that the original writer of this section was trying for something like this. Note that

$A=A^{T}$

$B=B^{T}$

$B=PAP^{T}$

where $P$ is a permutation matrix. Note that $P$ is unitary, therefore, I have replaced the 'inverse' operator with the transpose operator in all that follows. I have done the same with unitary matrices $Q_{A}$ and $Q_{B}$, below.

Since $A$ and $B$ are both symmetric, you can always diagonalize each with their respective (orthonormal) eigenvector matrices:

$A=Q_{A}\Lambda Q_{A}^{T}$

$B=Q_{B}\Lambda Q_{B}^{T}$

where the columns of $Q_{A}$ and $Q_{B}$ contain the unit-norm eigenvectors of $A$ and $B$, respectively.

Now, we can re-arrange the two above equations to eliminate $\Lambda$:

$\Lambda =Q_{B}^{T}BQ_{B}=Q_{A}^{T}AQ_{A}$

The right side of the above equality can further be re-arranged, using the fact that $Q_{B}^{-1}=Q_{B}^{T}$:

$B=Q_{B}Q_{A}^{T}AQ_{A}Q_{B}^{T}$

But we are given:

$B=PAP^{T}$

So that:

$PAP^{T}=Q_{B}Q_{A}^{T}AQ_{A}Q_{B}^{T}$ (*)

From (*), I believe that the original writer (incorrectly) concluded that $P$ must be equal to $Q_{B}Q_{A}^{T}$.

I cannot convince myself that this is true. In fact, I ran a few examples in Octave using permutations of randomly-generated symmetric matrices, and none of them seemed to work. Since both $P$ and $Q_{B}Q_{A}^{T}$ are unitary, and since (according the article) all permutation matrices are 'extreme points' of the space of unitary matrices, is there a way to find a unique $P$ that satisfies (*)? —Preceding unsigned comment added by Baddogsprocket (talk • contribs) 08:23, 25 March 2009 (UTC)

Take A to be the identity matrix to see that there is no unique solution. JackSchmidt (talk) 13:13, 25 March 2009 (UTC)

Well in that case, B would be identity as well, in which case we wouldn't be going through all of this. I think that's a more or less degenerate case because any vector is an eigenvector of a scaled identity matrix. What about other cases? —Preceding unsigned comment added by 70.190.74.211 (talk) 15:38, 25 March 2009 (UTC)

The problem is precisely degeneracy. Take A to be any symmetric matrix with a repeated eigenvalue, then clearly one can choose uncountably many distinct sets of eigenvectors, each set giving rise to several "Q". The distinct choices of P correspond to the distinct ways of ordering elements of that set while respecting eigenvalues. In group theory terms, you are just computing a centralizer, and unless the matrix is sufficiently general, the centralizer will be degenerately large. JackSchmidt (talk) 15:51, 25 March 2009 (UTC)

I actually thought of the repeated eigenvalue case today while I was at work. I have no group theory background. If you have no repeated eigenvalues, does the resulting matrix meet the definition of "sufficiently general?" If so, how far apart do the eigenvalues have to be before I can trust that a P-matrix I somehow magically find is the P-matrix? Is it something like the opposite of condition number, where instead of hoping that the maximum ratio of singular values is sufficiently close to unity, you hope the minimum ratio of singular values is sufficiently bounded away from unity? —Preceding unsigned comment added by Baddogsprocket (talk • contribs) 06:55, 26 March 2009 (UTC)

Consider a symmetric matrix C (for instance $C=Q_{B}Q_{A}^{T}AQ_{A}Q_{B}^{T}$). Suppose there are two permutation matrices P1 and P2 with P1* C P1 = P2* C P2. Then C = (P1 P2*) C (P1 P2*)*, and P = P1 P2* is itself a permutation matrix. There is a 1–1 correspondence between pairs of permutations matrices (P, P2) such that C = P C P* (that is, C P = P C) and P2 arbitrary, and pairs of permutation matrices (P1, P2) with P1* C P1 = P2* C P2.

Therefore, I confine my attention to classifying the "P" and ignoring the P1, P2. If C is diagonal and has distinct entries, then there is exactly one such P, the identity matrix. If C is diagonal and has eigenvalue multiplicities k1, k2, ..., kr, then there are exactly k1! k2! ... kr! such P (since they can arbitrarily reorder the diagonal entries that are equal without changing C). If C is not diagonal, it is more complex. JackSchmidt (talk) 21:04, 26 March 2009 (UTC)

I looked up Centralizer here and found if $a$ is a member of group $G$, then the Centralizer $C_{G}(a)$ is the set of all elements $x$ in $G$ that commute with $a$, in other words, $xa=ax$. I'm not sure how that fits in here, since $PA$ is not necessarily equal to $AP$. Are the centralizers you are talking about somehow related to the eigendecompositions of $A$ and $B$ themselves?

Every time I try to read anything about Abstract Algebra, I end up becoming enmeshed in tangled mass of nested jargon. Which would be okay if I could find a discernable entry point. —Preceding unsigned comment added by 70.190.74.211 (talk) 22:15, 28 March 2009 (UTC)

It is not true in general. Self-adjoint matrices (i.e., symmetric for real-valued matrices) can be diagonalized and the eigenvectors chosen to be orthogonal. However, in the case of repeated eigenvalues, there are an infinite number of ways to chose the orthogonal basis for the associated eigenspace, see "The Symmetric Eigenvalue Problem", B.N. Parlett, pp. 7-10. The example given is a real-valued, symmetric matrix so it can be diagonalized. Also, the eigenvalues are unique so each eigenspace is spanned by exactly one eigenvector, implying you can determine the permutation.Ebarszcz (talk) 21:14, 20 August 2010 (UTC)

I deleted the section due to the issues with it. -- Jitse Niesen (talk) 09:31, 30 July 2013 (UTC)

Right Multiply

Shouldn't a part be added to say that the multiplication of P on the right of a matrix M (instead of multiplying P by M, as in left multiplication, multiply M by P), will cause a permutation of the columns of M, in an analogous manner as it permutes the rows in left multiplication? I think a proof of both should also be included. If no one posts a proof or an explanation, I will do so myself here in the talk page, and then it can be edited.Goldencako 15:49, 14 November 2007 (UTC)

Graphical Representation?

Could anyone who happens to have some time & the wisdom provide a graphical representation somewhere on this? E.g., the "projection matrix page" has a great example of what the matrix is actually doing, "in real life". For instance, a 2-D projection matrix can project a 3-D object onto that 2-D plane.

I have some vague sense that a permutation matrix is changing the direction of a vector (or matrix) without changing its magnitude, just from looking at the math (and it somehow seems "obvious" to me, to abuse a term). But since the permutation matrix itself is an orthogonal matrix, I am also getting the sense that it is changing the direction of a vector (or matrix) in some way that is orthogonal to the original. But I cannot get my head around what that "looks" like; I cannot get an intuitive sense of what's going on, and therefore cannot imagine how I'd use this future applications.

--Mike Williamson —Preceding undated comment added 02:40, 27 December 2011 (UTC).

Example images

$\pi ={\begin{pmatrix}0&1&2&3&4\\1&3&0&2&4\end{pmatrix}}=(0132)(4)$
Left action (prefix) $M{\bigl (}\pi (i),i{\bigr )}=1$	Right action (postfix) $M{\bigl (}i,\pi (i){\bigr )}=1$
There are two ways to assign a matrix to a permutation, corresponding to the two ways of multiplying permutations. There are two ways to draw arrows in the chosen matrix, one similar to two-line and the other to cycle notation.

The table on the right was introduced by me, and then removed ("hid massive undecipherable table"), brought back and removed again ("hid unhelpful diagram") by Wcherowi.

I agree that the table can be a bit confusing, because it shows both ways of multiplication, but this confusion comes from reality and not from the table. I think it is necessary to show an example for both ways to assign a matrix to a permutation.

One could make the table clearer by removing the lower row with the cycles. But I think it is a good idea to show, that both two line and cycle notation can be seen in a permutation matrix. One could also make it clearer by adding labels on the left as in v:Permutation notation.

If I change the images from 0-based to 1-based permutations, the examples in the article could use the same permutation. Watchduck (quack) 13:27, 26 January 2017 (UTC)

To be clear about the editing history, I had introduced an error while attempting to correct the text and so I decided to self-revert and put the page back to its earlier form. This diagram was just an innocent bystander in this process. My original reasons for removing the diagram still stand. First of all, it is much too large; totally dominating the initial view of this article and making a point which is only a minor wrinkle in the subject. The diagram is not well integrated with the text of the article nor with the general literature on the subject. The major problem, however, is that unless the reader is quite familiar with the subject, these arrows passing through a stylized matrix do not convey much meaning. Although they make for a pretty picture a reader would be baffled by their intent. The concept involved has a much simpler explanation that I hope I have given in the text. The same problem exists with the diagrams appearing later in the article, but they might be saved by some appropriate text and I will need some time to consider how to do this. --Bill Cherowitzo (talk) 18:45, 26 January 2017 (UTC)

Definition

In the definition section, when say:

The $m\times m$ permutation matrix $P_{\pi }=(p_{ij})$ obtained by permuting the columns of the identity matrix $I_{m}$, that is, for each $i$, $p_{ij}=1$ if $j=\pi (i)$ and $0$ otherwise ...

Could be, in my opinion

The $m\times m$ permutation matrix $P_{\pi }=(p_{ij})$ obtained by permuting the columns of the identity matrix $I_{m}$, that is, for each $i$, $p_{ij}=1$ if $j=\pi (i)$ and $p_{ij}=0$ otherwise ... — Preceding unsigned comment added by Nikocof (talk • contribs)

Sure, that is clearer. I've made the change (in two places). --JBL (talk) 13:06, 17 March 2020 (UTC)

Permutation matrices are the non-negative orthogonal matrices

Users @JayBeeEll and @XOR'easter make the ridiculous claim that adding a sentence which notes that the permutation matrices can be precisely characterized as as the non-negative orthogonal matrices somehow magically "buries" and "obscures" other information in the article. Can these users explain their justification for this ridiculous claim? 2601:547:500:6940:D11A:50DC:8EB8:EDC0 (talk) 19:55, 5 August 2022 (UTC)

I'm not going to repeat the several full sentences I wrote about this in edit summaries, since you've clearly read them -- if there's something specifically you don't understand about them, let me know. It is totally possible that this characterization could be placed somewhere in the article (not in the place you put it), if you have an appropriate source for it. Do you? JBL (talk) 20:00, 5 August 2022 (UTC)

@JayBeeEll Your edit summaries were merely false assertions backed by absolutely nothing: no reasoning and no justification. And the place I put it was a good one because it was the place in the article where orthogonal matrices were mentioned. 2601:547:500:6940:D11A:50DC:8EB8:EDC0 (talk) 20:03, 5 August 2022 (UTC)

The fact that you don't understand something does not make it false. By the way, I've edited your addition (now in a more plausibly appropriate location) so that it is actually a true statement. Do you have a source for it? JBL (talk) 20:05, 5 August 2022 (UTC)

@JayBeeEll What exactly is it you claim I "don't understand"? Also, your edit makes no sense: Permutation and orthogonal matrices are real matrices, by definition. So there was nothing false about my statement. It seems like it's you who needs to review your definitions. I will add a source. 2601:547:500:6940:D11A:50DC:8EB8:EDC0 (talk) 20:09, 5 August 2022 (UTC)

The orthogonal group can be defined over any field. JBL (talk) 20:14, 5 August 2022 (UTC)

@JayBeeEll I said orthogonal matrices, not orthogonal group, did I not? 2601:547:500:6940:D11A:50DC:8EB8:EDC0 (talk) 20:23, 5 August 2022 (UTC)

An orthogonal matrix is an element of an orthogonal group; they can be defined over any field. (If you had followed the link I included and read the introductory section, you would have learned this!) Of course more people study O_n(R) than any other orthogonal group, but that doesn't make the other ones not exist. JBL (talk) 20:28, 5 August 2022 (UTC)

@JayBeeEll I expected you to reply with these ridiculous mental gymnastics. Orthogonal matrix, without qualification, simpliciter, refers to real matrices (and the same is true for "orthogonal group"). That's why, e.g., unitary matrices and unitary group are referred to by their own name. I can pull up various textbooks to support this, but it would be an exercise in futility since you already know I'm right. 2601:547:500:6940:D11A:50DC:8EB8:EDC0 (talk) 20:40, 5 August 2022 (UTC)

What you do not understand (apparently -- though I think you probably are perfectly capable of understanding it, once you get over your pique about being reverted) is that taking a sentence about topic X with a straightforward logical structure, splitting it into two sentences, and then inserting a separate sentence about topic Y into the middle of the two, obscures and obfuscates the original point X. Since the fact X (that permutation matrices are invertible, and their inverses are equal to their transposes) is really important, this is a bad thing to do. JBL (talk) 20:19, 5 August 2022 (UTC)

@JayBeeEll What really "piques" me is that you decided to unilaterally expunge the information from the article completely instead of rewording or moving it if necessary, which is what would be implied by your edit summary. 2601:547:500:6940:D11A:50DC:8EB8:EDC0 (talk) 20:49, 5 August 2022 (UTC)

I will add a source. That would be great, thank you in advance. JBL (talk) 20:20, 5 August 2022 (UTC)

To transpose or not to transpose, that is the question

This discussion was originally started on my user talk page; with permission, I am relocating it here. It refers to this edit, which I reverted. --JBL (talk) 19:11, 23 January 2024 (UTC)

Regarding one of your last edits in the permutation matrices article: I think the way that the introduction is written is somewhat misleading in the current state. While you are right that it is true that a permutation matrix multiplied from the left permutes the rows, i.e., $PM$ and from the left the columns $MP$, for the same permutation matrix $P$, this would lead to inconsistent permutations, because if $P$ multiplied from the right leads to a permutation according to, e.g., $1->2->3->1$, permutations with $P$ from the left lead to $1->3->2->1$. That's why I agree with the previous edit transposing the permutation matrix. I'm quite new here, so I am not sure if this is the right place to discuss this, I just think it would help intuitive understanding of the article. J-s-schmidt1 (talk) 13:55, 22 January 2024 (UTC)

Hi J-s-schmidt1, thanks for your message. In my opinion, the introduction currently engages in what might be called strategic vagueness: it says that multiplying a matrix on the left by a permutation matrix permutes the rows, but it does not say how it permutes the rows, and likewise it says that multiplying a matrix on the right by a permutation matrix permutes the columns, but it does not say how it permutes the columns. These statements are undoubtedly correct, but a reader who wishes to do concrete computations will find them not entirely satisfactory (because of the missing how) and will have to go read the body for details. In my opinion, this is a good arrangement of things. The added text makes the situation much more puzzling because it tells you what happens when you multiply by a permutation matrix on the left, and what happens when you multiply by the transpose of a permutation matrix on the right ... but there's nothing to explain why you would consider that combination. To fix this would require adding details about how multiplying by permutation matrices permutes the rows and columns to the lead, and in my opinion there's not reasonable way to do that without regurgitating the entire body section in the lead -- and that seems like a bad idea to me. --JBL (talk) 19:11, 23 January 2024 (UTC)

Hi @JayBeeEll, first of all, thank you so much for engaging in the discussion. We agree that this is a pure question of style and the statements as they are are correct without doubt. I also agree that for someone learning about permutation matrices, the style you suggest and the side is written in, totally makes sense because it engages the person to read more about it. However, for example for someone like me, Wikipedia has an encyclopaedic function, meaning oftentimes I just want a clear statement on the working right in the beginning. This is how we came to change the article as well, because we had to use permutation matrices and stumbled across the "missing" transpose. A proposition, how it would be clearer in my opinion, would be to change the sentence in the beginning to:

"Pre-multiplying an n-row matrix M by a permutation matrix P, forming PM, results in permuting the rows of M, while post-multiplying an n-column matrix M, forming $MP^{\mathsf {T}}$, permutes the columns of M in the same fashion."

Alternatively, we suggest to note the inversion:

"Pre-multiplying an n-row matrix M by a permutation matrix P, forming PM, results in permuting the rows of M, while post-multiplying an n-column matrix M, forming MP, permutes the columns of M inversely." J-s-schmidt1 (talk) 09:26, 25 January 2024 (UTC)