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