I have an expression of the form:


where $C$ is an invertible, symmetric and positive definite matrix. I'm trying to figure out if the expression above is invertible. The $C$ matrix is $n \times n$ and the $A$ matrix is $k \times n$. Every row of A has exactly one entry =1 and one entry =-1, all other entries are 0.

Any help, especially something pointing to a theorem, would be greatly appreciated.

  • $\begingroup$ Welcome to SciComp! What is the connection here to computational science? Typically, we use the answer to this question to determine topicality of questions like these on our site. If there's a strong relationship to computational science, the question is absolutely on-topic. If there's a weak connection to computational science, we tend to migrate the question elsewhere. We also tend to migrate questions if we feel that they would not be answered well here, and they would be answered well somewhere else. $\endgroup$ Jan 21 '14 at 20:38
  • 1
    $\begingroup$ I have an LP where my matrix C and A will be changing given the state of the system and I would like to be able to determine whether my system will ever be infeasible. I hope that fits within this group but please let me know $\endgroup$
    – evgeny
    Jan 21 '14 at 20:42
  • $\begingroup$ Is $k$ larger than $n$? Smaller than $n$? $\endgroup$ Jan 22 '14 at 4:35
  • $\begingroup$ smaller than n. I think that if A is of full rank (i.e. k) then this should be invertible, otherwise it's probably never invertible? $\endgroup$
    – evgeny
    Jan 22 '14 at 5:04

If $C\in\mathbb{R}^{n\times n}$ is (symmetric and) positive definite and $A\in\mathbb{R}^{k\times n}$ with $k\leq n$, then $ACA^T\in\mathbb{R}^{k\times k}$ is invertible if and only if $A$ has full rank. (You can think of $ACA^T$ as the projection of $C$ onto the subspace spanned by the rows of $A$, so it makes sense to expect them to be linearly independent.)

To see this, let $x\in\mathbb{R}^k\setminus\{0\}$ be arbitrary. If $A$ has full (row) rank, then $A^T$ has full (column) rank as well and thus is injective. Hence, $y:=A^Tx \in\mathbb{R}^n\setminus\{0\}$, and the positive definiteness of $C$ yields $$ x^T(ACA^T)x = (A^Tx)^TC(A^Tx) = y^TCy > 0, $$ i.e., $ACA^T$ is (symmetric and) positive definite and thus invertible. Conversely, if $A$ does not have full rank, $A^T$ is not injective and there exists a vector $x\in\mathbb{R}^k\setminus\{0\}$ with $A^Tx = 0$ and hence $ACA^Tx = 0$. It follows that $ACA^T$ is not injective and thus not invertible.

  • 1
    $\begingroup$ And with one nonzero entry per row, $A$ will have full row rank as long as the nonzero entries are all in different columns of $A$. $\endgroup$ Jan 22 '14 at 13:11
  • $\begingroup$ thanks Christian, that makes sense. My A matrix is an incidence matrix for a transmission network so as long as I don't have parallel lines, it should work out. $\endgroup$
    – evgeny
    Jan 22 '14 at 22:00

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.