Why is this formula positive definite? I have a formula
$$A(I+GQ)^{-1}(G+GQG)(I+QG)^{-1}A^{\mathrm T}+G$$
where $A,Q,G,I\in\mathbb R^{n\times n}$, $A$ nonsingular, $G$ positive semi-definite, $Q$ positive definite, $I$ the identity matrix, and $(A,G)$ controllable. It is obvious that both the first and second terms are positive semi-definite, but why this formula is positive definite in fact? Thanks in advance.
 A: It is not obvious that the matrix should be SPD but you can try to inspect the kernels of the two terms. Given two SPSD matrices $A$ and $B$, the sum $A+B$ is positive definite iff there is no nonnzero $x$ such that $x^TAx=-x^TBx$. Note that both $x^TAx$ and $x^TBx$ are nonnegative, so $x^TAx=-x^TBx$ iff $x^TAx=-x^TBx=0$, that is, iff $Ax=0$ and $Bx=0$. Equivalently, $x\in\mathrm{ker}(A)\cap\mathrm{ker}(B)$. Therefore, $A+B$ is SPD iff $\mathrm{ker}(A)\cap\mathrm{ker}(B)$ contains only the zero vector.
Another useful observation is that the kernel of $M=G+GQG$ is the same as the kernel of $G$. The matrix in question can be written as
$$\tag{♣}
A(I+GQ)^{-1}(G+GQG)(I+QG)^{-1}A^T+G=BMB^T+G,
$$
where $B=A(I+GQ)^{-1}$ and $\mathrm{ker}(M)=\mathrm{ker}(G)$.
Let $Z\in\mathbb{R}^{n\times k}$ be the basis of the kernel of $G$ ($\mathrm{im}(Z)=\mathrm{ker}(G)$, $\dim\mathrm{ker}(G)=k$). Then $Y=B^{-T}Z=A^{-T}(I+QG)=A^{-T}Z$ is the basis of the kernel of $BMB^T$. Following the development in the first paragraph, you require that these kernels have only a zero common vector. Equivalently, we need that
$$\tag{♥}
\mathrm{rank}([Z,A^{-T}Z])=\mathrm{rank}([Z,A^TZ])=2k.
$$
Summarizing,

(♣) is SPD iff (♥) holds.

Few observations:


*

*If $2\dim\mathrm{ker}(G)>n$ (as in the example of the other answer) then (♣) is always singular.

*According to the Popov-Belevich-Hautus (PBH) test, $(A,G)$ is controllable iff $Gv=0$ and $A^Tv=\lambda v$ implies $v=0$. However, (♥) says something slightly different. It says that if $Gv=0$ and $Gw=0$ such that $v=A^Tw$, then $v=w=0$. For me, this condition looks stronger than the controllability (but includes it too) and if the kernel of $G$ is one-dimensional, it is equivalent to the PBH test.

(♣) is SPD iff $Gv=Gw=0$ such that $A^Tw=v$ implies $v=w=0$.

A: The sum is not necessarily positive definite. For a counterexample, consider
$$
A = \pmatrix{5&2&0\\ 2&2&1\\ 0&1&1},\quad Q=I,\quad G=\pmatrix{1\\ &0\\ &&0}.
$$
It is straightforward to verify that $A$ is nonsingular (it has unit determinant) and $(A,G)$ is  controllable (the matrix $\pmatrix{G&AG&A^2G}$ has full row rank). Yet,
$$
A(I+GQ)^{-1}(G+GQG)(I+QG)^{-1}A^T+G = \pmatrix{\tfrac{27}2&5&0\\ 5&2&0\\ 0&0&0},
$$
which is singular.
However, the sum is positive definite when $\operatorname{rank}(G)\ge n-1$ (in particular, it is always PD for $2\times2$ matrices), essentially because the null space of $G$ is at most one-dimensional.
Edit.
To prove that the above rank condition is sufficient, we do some absorptions of matrices first, with $G\leftarrow Q^{1/2}GQ^{1/2}$ and $A\leftarrow Q^{1/2} A Q^{-1/2}$. Note that the new $(A,G)$ is also controllable; the new $A$ is still full-rank and the new $G$ is still PSD. With these absorptions, the given expression reduces to $Q^{-1/2}\left[A(I+G)^{-1}G A^T + G\right]Q^{-1/2}$. It is positive definite if and only if
$$P=A(I+G)^{-1}G A^T + G$$
is positive definite. As the OP mentions, the sum is always PSD. So the remaining question is when is $P$ singular. As both summands in $P$ are PSD, if $Px=0$, we must have $A(I+G)^{-1}G A^Tx=0$ and $Gx=0$. As $A(I+G)^{-1}$ is nonsingular, this set of conditions, when transposed, reduces to $x^TAG=0$ and $x^TG=0$.
However, by the PBH test of controllability, if $x^TG=0$ has a nontrivial solution, $x$ cannot be a left eigenvector of $A$. In other words, if $P$ is singular, $x^TA$ and $x^T$ are linearly independent and the left null space of $G$ is at least two-dimensional. Therefore, if $\operatorname{rank}(G)\ge n-1$ (i.e. $\operatorname{nullity}(G)\le1$), then $P$ is nonsingular, thus positive definite.
