# Help with permutation lemma for PA=LU.

I am trying to prove that for any permutation matrix P.

(I + c$$E_{i,j}$$)P = P(I + c$$E_{si,sj}$$)

My approach so far: $$P^{-1}$$(I + c$$E_{i,j}$$)$$P$$ = ($$P^{-1}$$ + c$$P^{-1}$$ $$E_{i,j}$$)$$P$$

= I + c$$P^{-1}$$ $$E_{i,j}P$$

Now i only need to show c$$P^{-1}$$ $$E_{i,j}P$$ = c$$E_{si,sj}$$

I tried doing this by using P = $$\sum_{i} E_{i, si}$$ And that $$P^T$$ = $$P^{-1}$$.

I am also using the fact, $$E_{i,j}E_{kl}$$ = $$\delta_{j,k}E_{i,l}$$.

Ok here is my thinking.

c$$P^{-1}$$ $$E_{i,j}P$$ = c$$(\sum_{i}E_{si,i})E_{i,j}(\sum_{j}E_{j,sj})$$ = c$$\sum_{i,j}E_{si,i}E_{i,j}E_{j,sj}$$

= c$$\sum_{i,j}\delta_{i,j}E_{si,i}E_{j,sj}$$ = c$$\sum_{i,j}\delta_{i,j}\delta_{i, j}E_{si,sj}$$ = c$$E_{si,sj}$$ When i=j.

Is this correct? wouldn't the condition i=j screw this up? This proof does not feel convincing, and i have no idea why.

Edit i noticed a mistake. Should be

c$$\sum_{i,j}\delta_{i,i}\delta_{j, j}E_{si,sj}$$ = c$$E_{si,sj}$$ when i=i, j=j

This feels more right, but i still would love some input if this is correct, and if a more straight forward proof is available.

Edit: After a helpful comment i used indices (k,l) for the permutation matrix so it would not interfere with the fixed (i,j), this led me to this calculation.

c$$P^{-1}$$ $$E_{i,j}P$$ = c$$(\sum_{k}E_{sk,k})E_{i,j}(\sum_{l}E_{l,sl})$$ = c$$\sum_{k,l}E_{sk,k}E_{i,j}E_{l,sl}$$

= c$$\sum_{k,l}\delta_{k,i}E_{sk,j}E_{l,sl}$$ = c$$\sum_{k,l}\delta_{k,i}\delta_{j, l}E_{sk,sl}$$ = c$$E_{sk,sl}$$ When k=i and j=l, thus = c$$E_{si,sj}$$

• If you start with $E_{ij}$ then $i,j$ are fixed. No good to use the same $i,j$ as summation indices. Another comment: any $P$ is a product of some very simple permutations. It is enough to prove for them only. – A.Γ. Aug 14 at 15:57
• I see so i should have used new indices like kl. Have to check if the proof is still valid in that case. I am not sure what you mean with your last statement though. – proeng Aug 14 at 16:07
• Any permutation is a composition of transpositions. Thus, to prove $MP_1P_2\ldots P_n=P_1P_2\ldots P_nM$ it is enough to prove $MP_i=P_iM$ where $P_i$ is a transposition. – A.Γ. Aug 14 at 16:10
• Yes and this is what this proof is supposed to do. A single permutation matrix can be written on the other side of an elementary matrix. I am thinking how to change the proof above to use k,l also. But i am not sure how to arrive at result, si, sj if i use k,l. Looking forward to see peoples suggestions for a proof. – proeng Aug 14 at 16:13