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

<p>No, multiplication by a permutation matrix will never change the rank of the matrix.  Permutation matrices are orthogonal, so if matrix M has an <a href="http://en.wikipedia.org/wiki/Singular_value_decomposition" rel="nofollow">SVD</a>:
$$ 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).</p>

CC BY-SA 3.0
2013-06-11T02:17:30.353Z
ok - thanks for the answer and for pointing me to a better place!
msg
CC BY-SA 3.0
2013-06-11T06:44:44.080Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-06-10T23:44:30.603Z
2013-06-10T23:44:30.603Z
Max Hutchinson
<p>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?</p>

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

<p>M2 = M P</p>

CC BY-SA 3.0
2013-06-11T00:06:49.673Z
This could be moved to http://scicomp.stackexchange.com/
Max Hutchinson
CC BY-SA 3.0
2013-06-11T01:04:17.900Z
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](http://cstheory.stackexchange.com/help/on-topic) for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.
Kaveh
<linear-algebra><permutations><matrix-product>
the product of a matrix and a permutation matrix
msg
# the product of a matrix and a permutation matrix

(Asked by: username_0 on 2013-06-10)

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

**Tags:** linear-algebra, permutations, matrix-product
> **Comments:**
> **username_1**: This could be moved to http://scicomp.stackexchange.com/  
> **username_2**: 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](http://cstheory.stackexchange.com/help/on-topic) for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.  

---

## 1 answers

### Answer by username_1 on 2013-06-10. Score: 1 | Accepted answer

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](http://en.wikipedia.org/wiki/Singular_value_decomposition):
$$ 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).

> **Comments:**
> **username_0**: ok - thanks for the answer and for pointing me to a better place!  
> **username_3**: 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.  

---

