Express $\mathrm{Tr}(X)$ in terms of $A$, given that $X=A^TX(I+X)^{-1}A$

Solution 1:

$X=A^TX(I+X)^{-1}A=X=A^T(X+I-I)(I+X)^{-1}A=A^TA-A^T(I+X)^{-1}A$.
$AXA^T = (AA^T)(AA^T)-AA^T (I+X)^{-1} AA^T$
$((AA^T))^{-1} AXA^T(AA^T)^{-1} = I-(I+X)^{-1}$
$ A^{-T} X A^{-1} = I-(I+X)^{-1}$
From this: if $X$ is a solution then $X^T$ is also a solution:
$ A^{-T} (X+X^T) A^{-1} = 2I-(I+X)^{-1}-(I+X^T)^{-1}$ Now $Tr(A^{-T} (X+X^T) A^{-1})=Tr( (X+X^T) (A^TA)^{-1})$
Hence the problem is reduced to finding trace of product of 2 symmetric matrices.\

a) Proceeding further with assumptions with equality:

1. Assume: $(A^TA)^{-1} = U \Sigma U^H$ and $X+X^T = U \Sigma' U^H$

$\sum_i \lambda_i((A^TA)^{-1}) 2\lambda_i(X) = 2n-2\sum_i \frac{1}{1+\lambda_i(X)}$. Now solve for $\{\lambda_i(X)\}$ for non-trivial solutions.With this u mighe be able to get a tight bound on $Tr(X)$.

2. You can use the equation (by assuming $A=U\Sigma U^H$ and $X=U\Sigma' U^H $): $ \frac{\lambda_i(X)}{\lambda_i(A)^2} = 1-\frac{1}{1+\lambda_i(X)}$ and solve for $\lambda_i(X)$.
   We get: $ \frac{\lambda_i(X)}{\lambda_i(A)^2} = \frac{\lambda_i(X)}{1+\lambda_i(X)}$
   Hence: $ \lambda_i(A)^2-1 = \lambda_i(X)$

b) Now proceeding without assumptions to get an inequality: Let $||A||_F$ be frobenius norm of $A$. $Tr(AB) \leq (||A||_F ||B||_F)^{1/2} = (\sum_i \lambda_i(A)^2 \sum_i \lambda_i(B)^2)^{1/2}$
$Tr( (X+X^T) (A^TA)^{-1}) \leq 2(\sum_i \lambda_i((A^TA)^{-1})^2 \sum_i \lambda_i(X)^2)^{1/2}$
Hence we get:
$\sqrt{\sum_i \lambda_i((A^TA)^{-1})^2 \sum_i \lambda_i(X)^2)} \geq n-\sum_i \frac{1}{1+\lambda_i(X)}$

Solution 2:

Disclaimer : This solution is wrong, however I will leave it in case it can be useful to find a definitive solution.

Let $AA^T = U\Sigma U^T$ with $\Sigma$ diagonal. Let $Y=U (\Sigma-I) U^T$ (with eigenvalues larger than 0), then \begin{align*} A^T Y(I+Y)^{-1}A&=A^TU(\Sigma-I)\Sigma^{-1}U^TA\\ &=A^TUU^TA-A^TU\Sigma^{-1} U^TA\\ &=A^TIA-A^T(AA^T)^{-1}A\\ &=Y^T\\ &=Y \end{align*} So $Y$ is a solution to the given equation. This means that $\mathrm{Tr}(Y)=\mathrm{Tr}(AA^T)-n$.

Solution 3:

Avoid answering in comments. For $2\times 2$ case only. First we have an easy to prove lemma: $$ \det(I+X)=\det(A)^2 $$ In our case: $$ X = \begin{bmatrix} x_{11} & x_{12} \\ x_{21} & x_{22} \end{bmatrix} \quad ; \quad A = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} $$ Then we have: $$ \det(I+X) = (a_{11}a_{22}-a_{12}a_{21})^2 $$ And: $$ X = A^TX(I+X)^{-1}A = \\ \begin{bmatrix} a_{11} & a_{21} \\ a_{12} & a_{22} \end{bmatrix} \begin{bmatrix} x_{11} & x_{12} \\ x_{21} & x_{22} \end{bmatrix} \begin{bmatrix} 1+x_{22} & -x_{12} \\ -x_{21} & 1+x_{11} \end{bmatrix} / \det(I+X) \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} $$ After some tedious algebra, it follows that we have four non-linear equations with four unknowns.
Then we invoke MAPLE:

eqns := {
((a11*x11+a21*x21)*(x22+1)-(a11*x12+a21*x22)*x21)*a11+(-(a11*x11+a21*x21)*x12+(a11*x12+a21*x22)*(x11+1))*a21 = x11*(a11*a22-a12*a21)^2,
((a11*x11+a21*x21)*(x22+1)-(a11*x12+a21*x22)*x21)*a12+(-(a11*x11+a21*x21)*x12+(a11*x12+a21*x22)*(x11+1))*a22 = x12*(a11*a22-a12*a21)^2,
((a12*x11+a22*x21)*(x22+1)-(a12*x12+a22*x22)*x21)*a11+(-(a12*x11+a22*x21)*x12+(a12*x12+a22*x22)*(x11+1))*a21 = x21*(a11*a22-a12*a21)^2,
((a12*x11+a22*x21)*(x22+1)-(a12*x12+a22*x22)*x21)*a12+(-(a12*x11+a22*x21)*x12+(a12*x12+a22*x22)*(x11+1))*a22 = x22*(a11*a22-a12*a21)^2};
solve(eqns,{x11,x12,x21,x22});
assign(s[2]);
x11+x22;

The latter two statements because we are not interested in the zero solution and seek for the trace. The end-result is: $$ \mathrm{Tr}(X) = \frac {-2-2a_{11}a_{21}a_{22}^3a_{12}+a_{11}^2a_{22}^4-2a_{11}a_{22}a_{12}^3a_{21} +4a_{11}a_{22}-2a_{12}a_{21}a_{11}^3a_{22}-2a_{11}^2a_{22}^2+2a_{12}^2a_{21}^2+a_{22}^2+a_{11}^2 -a_{21}^2-a_{12}^2 -2a_{21}^3a_{11}a_{22}a_{12}+a_{21}^4a_{12}^2+a_{12}^2a_{21}^2a_{22}^2 +a_{21}^2a_{11}^2a_{22}^2+a_{11}^2a_{12}^2 a_{21}^2+a_{11}^2a_{22}^2a_{12}^2+a_{12}^4a_{21}^2 +2a_{22}^2a_{21}a_{12}-2a_{22}^3a_{11}-2a_{22}a_{11}^3+a_{11}^4 a_{22}^2+2a_{11}^2a_{21}a_{12}} {1+a_{21}^2+a_{11}^2a_{22}^2-2a_{11}a_{22}a_{12}a_{21}+a_{12}^2a_{21}^2+a_{12}^2-2a_{11}a_{22}} $$