-3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ This could be moved to scicomp.stackexchange.com $\endgroup$
    – Max Hutchinson
    Jun 11, 2013 at 0:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jun 11, 2013 at 1:04

1 Answer 1

Reset to default
1
$\begingroup$

This probably doesn't belong on the TCS stack exchange, but I'll answer anyways.

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ ok - thanks for the answer and for pointing me to a better place! $\endgroup$
    – msg
    Jun 11, 2013 at 2:17
  • 4
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Jun 11, 2013 at 6:44

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