# rank of $ACA^T$

Let $A$ be a $m\times n$ matrix with $n\sim m^2$ and with rank $m$, and $C$ a $n\times n$ permutation matrix of order 2. Is it true that $ACA^T$ is always invertible? or in some special cases?

If it helps: you may assume $A$ is in row echelon form with all entries being 0 or 1.

• What do you mean by $n\sim m^2$, Adam? – David Roberts Oct 9 '16 at 8:27
• The amount of columns is about the square of the amount of rows – Adam Gal Oct 9 '16 at 9:38
• ah, I thought that might be it, but I wasn't sure. – David Roberts Oct 10 '16 at 0:10

Not always. To see this, compute the compact SVD of $A$ to obtain $$A = U \Sigma V^T$$ where $U$ is an $m \times m$ orthogonal matrix, $\Sigma$ is $m \times m$ diagonal matrix with positive diagonal entries corresponding to the $m$ singular values of $A$, and $V$ is $n \times m$ matrix with orthonormal columns. This gives the decomposition: $$A C A^T = U \Sigma V^T C V \Sigma U^T$$ and so, $$\det(A C A^T) = \det(U)^2 \det(\Sigma)^2 \det(V^T C V)$$ where $V^T C V$ is an $m \times m$ matrix.
Since $U$ is an $m\times m$ orthogonal matrix and the $m$ singular values of $A$ are positive, we reduced the problem to checking the rank of the $m \times m$ matrix $V^T C V$. However, a $n \times n$ permutation matrix acting on a set of $m$ orthonormal vectors (where $n>m$) may alter the $m$-dimensional subspace which they span. In order to avoid this possibility, one must verify that $\text{col}(CV)=\text{col}(V)$, which imposes certain restrictions on the $n \times n$ permutation matrix $C$.