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