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.

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

  • $\begingroup$ Thanks! however, that last condition is very much not the situation I have. The thing is that I know the matrix is invertible from other considerations but was trying to give a different proof. $\endgroup$ – Adam Gal Oct 10 '16 at 9:26
  • $\begingroup$ Since the columns of V (the right singular vectors) form an orthonormal basis for the column space of A', the last condition can be equivalently stated as: the permutation matrix C leaves the column space of A' invariant. If your matrix is invertible, it must be that this condition is satisfied by your C. $\endgroup$ – Nawaf Bou-Rabee Oct 10 '16 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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