A System of Matrix Equations with a Surprising Property

linear algebramatricesmatrix equations

Setup

Let $\mathbf a$ be an arbitrary $m\times 1$ vector, and $\mathbf B$ be an arbitrary $n\times m$ matrix, with $m>n$. Let $\mathbf K$ be the $m\times u$ given by
$$\mathbf K = \left[\begin{array}{c}\mathbf I_u\\ \mathbf{0} \end{array} \right],$$
where $m>u$.

The $n\times 1$ vector $\mathbf h$ satisfies the following fixed point problem:
\begin{align*}
\mathbf h = & \;\left(\mathbf B {\mathbf \Omega}\mathbf B'\right)^{-1}\mathbf B{\mathbf\Omega}\mathbf{KK'a} ,\\[2ex]
\mathbf {\Omega} =&\;\mathbf I_m +\mathbf{K } \mathbf W\mathbf K' ,\\[2ex]
\mathbf W = &\;\left\{ \mathbf I_u- \mathbf K'\left(\mathbf B^{\prime}\mathbf h -\mathbf a \right)\left(\mathbf h'\mathbf B-\mathbf a' \right)\mathbf K\right\}^{-1}.
\end{align*}


Conjecture

There exists a scalar $\gamma$, such that $\mathbf h$ satisfies
$$
\mathbf h = \left(\mathbf B \mathbf\Gamma \mathbf B'\right)^{-1}\mathbf B\mathbf{ KK'a} ,
$$

where
$$ \mathbf\Gamma = \left[\begin{array}{cc}\mathbf I_u &\mathbf{0} \\
\mathbf{0}&\gamma\mathbf I_{m-u}\end{array} \right].$$


Updates:

  • We found a formula for $\gamma$:
    $$\gamma=\frac{1-r}{2-r},\qquad\text{where } r=\left(\mathbf h'\mathbf B-\mathbf a' \right)\mathbf {KK'}\left(\mathbf B^{\prime}\mathbf h -\mathbf a \right).$$
    I also updated the code below, since it is more stable with this formula.
  • It follows from the Sherman-Morrison formula that
    $$\mathbf W = \mathbf I_u + \frac{\mathbf K'\left(\mathbf B^{\prime}\mathbf h -\mathbf a \right)\left(\mathbf h'\mathbf B-\mathbf a' \right)\mathbf K}{1-r}.$$

We have tested this conjecture numerically thoroughly and are pretty convinced it is true, but have not been able to prove it. Any help would be much appreciated.

As background, the fixed point problem comes from a variation on a linear forecasting problem with ambiguity aversion.

Here is a simple Matlab code that allows you to test the result:

clear

% Parameters:

n = 3;
u = 4;
m = 6;

a = randn(m,1);
B = randn(n,m);
K = [eye(u);zeros(m-u,u)];

% Find fixed point for h:

ite    = 0;
d      = 1;
maxite = 1000;
tol    = 1e-10;
h0 =  (a'*(K*K')*B'/(B*B'))';
while (d>tol && ite<maxite)
    ite = ite+1;
    W   = eye(u)/(eye(u)-K'*(B'*h0-a)*(h0'*B-a')*K);
    Om  = eye(m)+K*W*K';
    h   = (a'*(K*K')*Om*B'/(B*Om*B'))';
    d   = max(abs(h-h0));
    h0  = h;
end

% Solve for gamma:

r = ((h0'*B-a')*(K*K')*(B'*h0-a));
gamma = (1-r)/(2-r);

h_gamma = (a'*(K*K')*B'/(B*[eye(u),zeros(u,m-u);zeros(m-u,u),gamma*eye(m-u)]*B'))';

disp(gamma)
disp([h,h_gamma])

Best Answer

We start with the relation $\mathbf h = \left(\mathbf B {\mathbf \Omega}\mathbf B'\right)^{-1}\mathbf B{\mathbf\Omega}\mathbf{KK'a}$ which gives $ \mathbf B {\mathbf \Omega}\mathbf B'\mathbf h = \mathbf B{\mathbf\Omega}\mathbf{KK'a}.$ Substituting $\mathbf \Omega=\mathbf{I}+\mathbf{KWK'}$, we get \begin{align} \mathbf B \left(\mathbf{I}+\mathbf{KWK}'\right)\mathbf B'\mathbf h &= \mathbf B\left(\mathbf{I}+\mathbf{KWK}'\right)\mathbf{KK'a}\\ \implies \mathbf B\mathbf{KK'a} &=\mathbf {B B}' \mathbf h +\mathbf{B}\mathbf{KWK}'\left(\mathbf B'\mathbf h -\mathbf{a}\right),\tag{1} \end{align} since $\mathbf{K'KK'}=\mathbf{K'}.$ Using the relation $\mathbf W = \left( \mathbf I- \mathbf K'\left(\mathbf B^{\prime}\mathbf h -\mathbf a \right)\left(\mathbf h'\mathbf B-\mathbf a' \right)\mathbf K\right)^{-1}$ and the Sherman-Morrison formula, we obtain \begin{align} \mathbf{KWK}'\left(\mathbf B'\mathbf h -\mathbf{a}\right)&=\mathbf{K}\left( \mathbf I- \mathbf K'\left(\mathbf B^{\prime}\mathbf h -\mathbf a \right)\left(\mathbf h'\mathbf B-\mathbf a' \right)\mathbf K\right)^{-1}\mathbf{K}'\left(\mathbf B'\mathbf h -\mathbf{a}\right)\\ &=\mathbf{K}\left( \mathbf I + \frac{\mathbf K'\left(\mathbf B^{\prime}\mathbf h -\mathbf a \right)\left(\mathbf h'\mathbf B-\mathbf a' \right)\mathbf K}{1-r}\right)\mathbf{K}'\left(\mathbf B'\mathbf h -\mathbf{a}\right)\\ &= \left( 1 + \frac{r}{1-r}\right)\mathbf{K}\mathbf{K}'\left(\mathbf B'\mathbf h -\mathbf{a}\right)= \frac{1}{1-r}\mathbf{K}\mathbf{K}'\left(\mathbf B'\mathbf h -\mathbf{a}\right)\tag{2}, \end{align} where $r\triangleq \left(\mathbf h'\mathbf B-\mathbf a' \right)\mathbf K\mathbf K'\left(\mathbf B^{\prime}\mathbf h -\mathbf a \right)\neq 1$. Combining $(1)$ and $(2)$, we arrive at \begin{align} \mathbf B\mathbf{KK'a} &=\mathbf {B B}' \mathbf h +\frac{1}{1-r}\mathbf{B}\mathbf{K}\mathbf{K}'\left(\mathbf B'\mathbf h -\mathbf{a}\right)\\ \implies \frac{2-r}{1-r}\mathbf B\mathbf{KK'a} &= \mathbf {B}\left(\mathbf I+\frac{1}{1-r}\mathbf{K}\mathbf{K}'\right)\mathbf{ B}' \mathbf h\\ \implies \mathbf B\mathbf{KK'a} &= \mathbf {B}\left(\frac{1-r}{2-r}\mathbf I+\frac{1}{2-r}\mathbf{K}\mathbf{K}'\right)\mathbf{ B}' \mathbf h.\tag{3} \end{align} Since $\mathbf{K}=\begin{bmatrix}\mathbf{I} \\\mathbf 0\end{bmatrix}$, we get that $$ \frac{1-r}{2-r}\mathbf I+\frac{1}{2-r}\mathbf{K}\mathbf{K}' = \frac{1-r}{2-r}\begin{bmatrix}\mathbf I &\mathbf 0\\ \mathbf 0&\mathbf I\end{bmatrix}+\frac{1}{2-r}\begin{bmatrix}\mathbf{I} \\\mathbf 0\end{bmatrix}\begin{bmatrix}\mathbf{I} &\mathbf 0\end{bmatrix} = \begin{bmatrix}\mathbf I &\mathbf 0\\ \mathbf 0& \frac{1-r}{2-r}\mathbf I\end{bmatrix}\triangleq \mathbf\Gamma.$$ Thus, $(3)$ yields $ \mathbf B\mathbf{KK'a} = \mathbf {B}\mathbf\Gamma\mathbf{ B}' \mathbf h\implies \mathbf h=\left(\mathbf {B}\mathbf\Gamma\mathbf{ B}'\right)^{-1}\mathbf B\mathbf{KK'a}.$ Here, $\mathbf {B}\mathbf\Gamma\mathbf{ B}'$ is invertible as $r\neq 1$ due to the Sherman-Morrison formula, and from the fact that $\mathbf B {\mathbf \Omega}\mathbf B'$ is invertible (i.e., $n=\mathrm{rank}\{\mathbf B\}=\mathrm{rank}\{\mathbf B\mathbf B'\} $).

Thus, the proof is complete.

Related Question