I have following three basic recurrence relations $$\mathcal U_{k+1}=A(I+\mathcal U_{k}Q)^{-1}\mathcal U_{k}A^{\mathrm T}+G\\ \mathcal V_{k+1}=\mathcal V_{k}(I+Q\mathcal U_{k})^{-1}A^{\mathrm T}\\ \mathcal W_{k+1}=\mathcal W_{k}+\mathcal V_{k}(I+Q\mathcal U_{k})^{-1}Q\mathcal V_{k}^{\mathrm T} $$ where all the matrices are square, $I$ is the identity, $A$, $Q$, $G$ are the given constant matrices that $A$ nonsingular, $Q\succeq O$, $G\succeq O$, $(A,G)$ controllable, $(Q,A)$ observable. $\mathcal U_{k}$, $\mathcal V_{k}$, $\mathcal W_{k}$ are variables, $\mathcal U_{0}=O$, $\mathcal V_{0}=I$, $\mathcal W_{0}=O$, $k=0,1,2,\cdots$. ($O$ is the zero matrix)
My question is how to prove the following?
- rank$(\mathcal W_{k+1})>$rank$(\mathcal W_{k})$ when $\mathcal W_{k}$ does not have full rank (positive semidefinite)
- rank$(\mathcal W_{k+1})=$rank$(\mathcal W_{k})$ when $\mathcal W_{k}$ has full rank (positive definite)
The second one is obvious since $\mathcal V_{k}$ is nonsingular, but how about the first one? Thanks in advance!
We can find
$$U_1=G,~~ U_2=A(I+GQ)^{-1}GA^T+G$$ $$V_1=A^T,~~ V_2=A^T(I+QG)^{-1}A^T$$ $$W_1=Q,~~ W_2=Q+A^T(I+QG)^{-1}QA$$
We also know that $(A,Q)$ is observable if and only if
$$\begin{bmatrix}Q \\ QA \\ \vdots \\ QA^{n-1}\end{bmatrix} v = 0$$
implies $v=0$.
Now suppose $\text{rank}Q=r$. Then there exists $n-r$ linearly independent vectors $v_i$ such that $Qv_i=W_1 v_i=0$. Now let us look at $W_2 v_i$,
$$\begin{align*} W_2 v_i &= (Q+A^T(I+GQ)^{-1}QA)v_i \\ &= A^T(I+GQ)^{-1}QAv_i \end{align*}$$
Since $A^T$ and $(I+GQ)^{-1}$ are full rank matrices, they do not affect the following discussion.
From the observability assumption $QAv_i \neq 0$ for some $v_i$.
If it was, $\text{Ker}Q$ would be $A$-invariant, i.e. $QA^kv_i=0$ for all $k>0$ and $v_i \in \text{Ker}Q$, which would be a contradiction to observability assumption.
Explanation: By definition $v \in \text{Ker}Q$ if $Q v = 0$. Let $Q A v = 0$ for all $v \in \text{Ker}Q$. This means $v_1 := Av \in \text{Ker}Q$ also. So, $Q A v_1 = Q A^2 v = 0$. Similarly, $Q A^k v = 0$ for all $v \in \text{Ker}Q$ and $k > 0$. More generally a subspace $\mathcal{S}$ is said to be $A$-invariant if $A v \in \mathcal{S}$ for all $v \in \mathcal{S}$. A good reference is here. What I wanted to say there must exist some vectors such that $Q v = 0$ but $Q A v \neq 0$ from the observability assumption.
Therefore, we conclude that $\text{rank}W_2 > \text{rank}W_1$ if $W_1$ is not full rank.
We now select the vectors in $v_i$ such that $QAv_i=0$ and denote them as $v'_i$. Note that the count of $v'_i$ must be less than $n-r$ from the previous discussion. We now know that $W_2 v'_i=0$, so let us look at $W_3 v'_i$.
$$\begin{align*} W_3 v'_i &= (W_2 + V_2 (I+QU_2)^{-1}QV_2^T)v'_i \\ &= V_2 (I+QU_2)^{-1}QA(I+QG)^{-T}Av'_i \end{align*}$$
Similarly, we can focus on $QA(I+QG)^{-T}Av'_i$ part. Here, we can use the Matrix Inversion Lemma to obtain
$$\begin{align*} QA(I+QG)^{-T}Av'_i &= QA(I-G^T(I+GQ)^{-T}Q^T)Av'_i \\ &= QA^2v'_i-G(I+GQ)^{-T}QAv'_i \\ &= QA^2v'_i \end{align*}$$
where we used the symmetricity of $G$ and $Q$. Similarly, $QA^2v'_i\neq0$ for some of the $v'_i$. Hence, $\text{rank}W_3 > \text{rank}W_2$.
By putting $U_k$ for $G$ in the above equations we can continue selecting $v$ such that $QA^kv=0$ from the set of vectors such that $QA^{k-1}v=0$ at each step. If at some point $\text{rank}W_k=n$, this means there is no vector exists that we can select from, hence $\text{rank}W_{k+1} = \text{rank}W_k$.
Explanation: We need to show that there exists vectors such that $W_k v = 0$ but $W_{k+1} v \neq 0$. This is the same as finding $v$ such that $Q V_k^T v = 0$ but $Q V_{k+1}^T v \neq 0$. I tried to show that this is also equivalent finding $v$ such that $Q A^{k} v = 0$ but $Q A^{k+1} v \neq 0$. To see that write the definition to obtain
$$\begin{align*} Q V_{k+1}^T v &= QA(I+QU_k)^{-T}V_k^T v \\ &= QA(I-U_k^T(I+U_kQ)^{-T}Q^T)V_k^T v \\ &= QAV_k^T v - QAU_k^T(I+U_kQ)^{-T}Q V_k^T v \\ &= QA V_k^T v \end{align*}$$
Since $V_1 = A^T$, it follows from the induction.