# the rank of matrix products including a commutation matrix

Given a full rank matrix $A \in \mathbb{R}^{M \times N^2}$ where the rank of ${A}$ is ${\rm rk}(A)= M \leq N^2$ and the commutation matrix $K_{NN}$. I need to find the rank of a matrix product $rk(A-AK_{NN}) = rk(A(I-K_{NN}))$. My conjecture (I am actually pretty sure) is that the rank should be $min(M, \frac{1}{2}N(N-1))$ where $\frac{1}{2}N(N-1)$ is the rank of $(I-K_{NN})$ known from the literature. Does anybody know how this can be done or at least give me a possible routine to follow?

The elements of A are generated from Gaussian distributions.

-

Your conjecture is wrong. Here is a counterexample: $A=\pmatrix{1&1&1&0\\ 0&1&1&1}$. We have $A(I-K_{2,2})=0$.
When $A$ is a random matrix whose entries are generated from i.i.d. Gaussian distributions, since $A(I-K_{N,N})\operatorname{vec}(X)=0$ for all symmetric matrix $X$, the rank of $L=A(I-K_{N,N})$ is the rank of $L$ restricted on the $\frac12N(N-1)$-dimensional subspace $\{\operatorname{vec}(X): X=-X^T\}$. Hence $\operatorname{rank}(L)=\min\left\{M,\ \frac12N(N-1)\right\}$ almost everywhere (but not everywhere, as the above counterexample illustrates).
For all symmetric $X$, $\mathrm{vec}(X)$ lies inside $\ker A(I-K)$. So, with an appropriate change-of-basis matrix $T$, we may assume that $I-K=T[C,0]T^{-1}$ where $C$ has rank $N(N-1)/2$ and the trailing zero block has $N(N+1)/2$ columns. Hence $$\mathrm{rank}(A(I-K))=\mathrm{rank}(AT[C,0]T^{-1})=\mathrm{rank}(AT[C,0])= \mathrm{rank}(ATC).$$ As $TC$ has full rank, $ATC$ has full rank almost everywhere. but $ATC$ is $M\times\frac12N(N-1)$. So, when it has full rank, its rank is $\min\{M,\,\frac12N(N-1)\}$. –  user1551 Nov 30 '13 at 0:20
Is the key point to transform $I-K$ into a full rank matrix? If yes, can I simply use the economic sized EVD? E.g., assume that $(I-K)(I-K)^{\rm T} = [Us, Un][Cs 0; 0,0][Us, Un]^{\rm T}$ and I have Us is $N^2 \times \frac{1}{2}N(N-1)$. Then $rank(A(I-K)) = rank(A(I-K)(A(I-K))^{\rm T}) = rank(AUsCs^{0.5}Cs^{0.5}Us^{\rm T}A^{\rm T} =rank(AUsCs^{0.5})$ where $UsCs^{0.5}$ has a full rank. Another question is which reference can I refer to for the conclusion $rank(AC) = rank(A)rank(C)$ given $A$ is random and $C$ is fixed but both of them is full rank. –  user111614 Dec 2 '13 at 16:36