Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a question from the free Harvard online abstract algebra lectures. I'm posting my solutions here to get some feedback on them. For a fuller explanation, see this post.

This problem is from assignment 4.

Prove that the transpose of a permutation matrix $P$ is its inverse.

A permutation matrix $P$ has a single 1 in each row and a single 1 in each column, all other entries being 0. So column $j$ has a single 1 at position $e_{i_jj}$. $P$ acts by moving row $j$ to row $i_j$ for each column $j$. Taking the transpose of $P$ moves each 1 entry from $e_{i_jj}$ to $e_{ji_j}$. Then $P^t$ acts by moving row $i_j$ to row $j$ for each row $i_j$. Since this is the inverse operation, $P^t=P^{-1}$.

Again, I welcome any critique of my reasoning and/or my style as well as alternative solutions to the problem.

Thanks.

share|improve this question
2  
Perhaps you could be clearer on what $P$ is acting upon and how. I think you're multiplying some unnamed matrix $A$ on the left by $P$ to get $PA$, but it would be good to spell this out. When you say "each column $j$" that's also a bit confusing, since you've already used $j$ for something. –  Dylan Moreland Jan 12 '12 at 19:55
5  
I think it would be clearer if you prove this first for permutation matrices corresponding to simple transpositions, as then $P$ will be an elementary matrix and we know what the inverse of elementary matrices are. Then use the fact that every permutation can be written as a product of transpositions, and that if $\sigma$ and $\rho$ are permutations, then $P_{\sigma\rho} = P_{\sigma}P_{\rho}$, to conclude the result for arbitrary permutations. But that's just me. –  Arturo Magidin Jan 12 '12 at 19:56
    
I also think it would be good to in the end show that $PP^t = (P^t)P = I_n$, where $I_n$ is the $n \times n$ identity matrix. This stuff about moving rows around isn't exactly wrong, though. –  Dylan Moreland Jan 12 '12 at 19:59
    
Another way of looking at this is to identify the permutation represented by the first matrix, compute the inverse permutation (easy), convert this to matrix form, and compare with the proposed inverse. –  Mark Bennet Jan 12 '12 at 20:18
1  
@jobrien929: I suspect that trying to write it out carefully would just lead to precisely my suggestion, considering transpositions or products of transpositions. Otherwise, keeping track of all the row shuffles is going to be a pain. Clarification: you may want to show only that if $\tau$ is a transposition and $\sigma$ a permutation, then $P_{\tau}P_{\sigma} = P_{\tau\sigma}$, rather than trying to prove it for any two permutations. That should be enough. –  Arturo Magidin Jan 12 '12 at 21:37

3 Answers 3

up vote 7 down vote accepted

A direct computation is also fine: $$(PP^T)_{ij} = \sum_{k=1}^n P_{ik} P^T_{kj} = \sum_{k=1}^n P_{ik} P_{jk}$$ but $P_{ik}$ is usually 0, and so $P_{ik} P_{jk}$ is usually 0. The only time $P_{ik}$ is nonzero is when it is 1, but then there are no other $i' \neq i$ such that $P_{i'k}$ is nonzero ($i$ is the only row with a 1 in column $k$). In other words, $$\sum_{k=1}^n P_{ik} P_{jk} = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{otherwise} \end{cases}$$ and this is exactly the formula for the entries of the identity matrix, so $$PP^T = I$$

share|improve this answer
    
Funny that we independently come up with almost identical answers. Since it seems you beat me to it, I can delete mine if you want. –  Jason DeVito Jan 12 '12 at 20:06

Using a little knowledge about orthogonal matrices the following proof is pretty simple:

Since $v^tw=\sum_{k=0}^nv_iw_i$ if $v=(v_1,...,v_n),w=(w_1,...,w_n)$ we have $v^tv=1$ whenever v is a column of $P$. On the other hand $v^tw=0$ if $v$ and $w$ are two distinct columns of $P$. Therefore we can conclude that $(P^tP)_{i,j}=\delta_{i,j}$ and so $P^t=P^{-1}$.

share|improve this answer

Less sophisticated, you could just crunch it out.

First, a lemma:

The inverse of a matrix, if it exists, is unique.

Proof: If both $B$ and $C$ are inverse to $A$, then we have $B = BI = B(AC) = (BA)C = IC = C$ so $B = C$. (Here, $I$ denotes the identity matrix).

Using this, it follows in our specific case that in order to show $A^t = A^{-1}$, we need only show $A^tA = A^t A = I$.

Assume $i\neq j$. Then $(AA^t)_{ij} = \sum_k A_{ik}A^t_{kj} = \sum_k A_{ik}A_{jk}$. But for each $k$, $A_{ik}A_{jk} = 0$ since there is only one nonzero entry in the $k$th row and $i\neq j$ (so $A_{ik}$ and $A_{jk}$ can't both be the nonzero entry). So, $(AA^t)_{ij} = 0$ when $i\neq j$.

The argument that $(A^tA)_{ij} = 0$ when $i\neq j$ is almost identical, but uses the fact that the columns of $A$ contain only one nonzero entry.

Can you see what happens when, instead, $i = j$?

share|improve this answer
    
Looks good to me too. A survey of style is probably good for this kind of question. –  Jack Schmidt Jan 12 '12 at 20:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.