# the product of a matrix and a permutation matrix [closed]

Can a permutation matrix (P) be used to change the rank of another matrix (M)? Is there any literature to this effect, or to the contrary?

I've tried a few small examples and the resulting matrix (M2) seems to always have the same rank as the input matrix (M)

M2 = M P

• This could be moved to scicomp.stackexchange.com Jun 11, 2013 at 0:06
• Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. Your question might be suitable for Computer Science which has a broader scope. Jun 11, 2013 at 1:04

No, multiplication by a permutation matrix will never change the rank of the matrix. Permutation matrices are orthogonal, so if matrix M has an SVD: $$M = U \Sigma V^*$$ Then the product $MP$ has an SVD: $$MP = U \Sigma V^* P = U \Sigma W^*$$ Recall that the rank is the number of non-zero singular values. Because $M$ and $MP$ have the same singular values $\Sigma$, they must have the same rank (and a whole bunch of other stuff).
• SVD is an overkill here (the existence of the decomposition is nontrivial to prove). All you need to note is that $MP$ is just $M$ with its columns permuted, which obviously doesn't change the number of linearly independent columns. Jun 11, 2013 at 6:44