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

Given real non-singular $$n\times n$$ matrix $$A$$, with all eigenvalues larger that $$1$$.

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

It is allowed to assume that $$A$$ is in any special form that can be obtained using similarity transformation, i.e. $$A$$ can be changed by $$\hat{A}$$, if $$A=P^{-1}\hat{A}P$$, for some nonsingular $$P$$.

My attempt: For symmetric $$A$$ case, WLOG we can assume $$A$$ is diagonal, then

\begin{align} X&=AX(I+X)^{-1}A\\ AX^{-1}AX&=I+X\\ AYA&=Y+I\\ (A\otimes A-I)\mathrm{vec}(Y)&=\mathrm{vec}(I)\\ \mathrm{vec}(Y)&=(A\otimes A-I)^{-1}\mathrm{vec}(I), \end{align}

where $$Y=X^{-1}$$ and $$\otimes$$ denotes Kronecker product.

If $$\mathrm{vec}(Y)=(A\otimes A-I)^{-1}\mathrm{vec}(I)$$, then $$\mathrm{vec}(X)=(A\otimes A-I)\mathrm{vec}(I)$$, using this result.

From last eq. it is easy to see that $$\mathrm{Tr}(X)=\sum_{i=1}^na^2_i-n$$, where $$a_i$$ are diagonal elements of $$A$$.

Assume that all eigenvalues of $$(A)$$ are equal to $$\lambda$$ and that Jordan canonical form of $$A$$ consists of single Jordan block $$J$$. Then

\begin{align} \mathrm{vec}(Y)&=(A\otimes A-I)^{-1}\mathrm{vec}(I)\\ &=\begin{bmatrix} \lambda J-I & J & && \\ &\lambda J-I&J& &\\ & & \ddots & \ddots& \\ & & & \lambda J-I & J \\ & & & & \lambda J-I \end{bmatrix}^{-1}\mathrm{vec}(I)\\ &=\begin{bmatrix} M & -MJM & MJMJM & \dots & (-1)^{n-1}MJM\cdots M \\ & \ddots & \ddots & \ddots & \ddots\\ & & M & -MJM & MJMJM\\ & & & M& -MJM\\ &&&&M \end{bmatrix}\mathrm{vec}(I)\\ &=\begin{bmatrix} TJ^{-1} & -T^2J^{-1} & T^3J^{-1} & \dots & (-1)^{n-1}T^nJ^{-1} \\ & \ddots & \ddots & \ddots & \ddots\\ & & TJ^{-1} & -T^2J^{-1} & T^3J^{-1}\\ & & & TJ^{-1}& -T^2J^{-1}\\ &&&&TJ^{-1} \end{bmatrix}\mathrm{vec}(I) \end{align}

where $$M=(\lambda J-I)^{-1}$$ and $$T=MJ=(\lambda I-J^{-1})^{-1}$$. Second last equation is obtained using Block matrix inversion formula. I am not sure what to do next, the expression looks too complicated. Maybe there is an easier way to do it?

EDIT: $$\qquad$$ For $$A=\begin{bmatrix} a_1 & 1\\ 0&a_2 \end{bmatrix}$$, we will get $$\mathrm{Tr}(X)=(a_1^2+a_2^2-2)+\frac{(a_1^2-1)(a_2^2-1)}{(a_1a_2-1)^2+1}$$.

$$\qquad$$ While For $$A=\begin{bmatrix} a_1 & 0\\ 0&a_2 \end{bmatrix}$$, we will get $$\mathrm{Tr}(X)=(a_1^2+a_2^2-2)$$.

The original problem is equivalent to the following problem:

Find $$\mathrm{Tr}(Z)$$, where $$A'Z^{-1}A+Z=A'A+I$$ and $$Z-I>0.$$

• For more general $A$, maybe you can exploit the property of the trace that $\mathrm{Tr}(BC) = \mathrm{Tr}(CB)$ and note that $A^TA$ is always symmetric. May 1, 2021 at 16:19
• A small trick: $X=A^T X(I+X)^{-1} A= A^T (I+X-I)(I+X)^{-1}A = A^TA + A^T(I+X)^{-1}A$.. See if this is useful. May 5, 2021 at 14:30
• If the matrix $A$ is assumed to be real & non-singular, then its eigenvalues might be complex. Could you please clarify what you mean by "all eigenvalues larger than $1$"? May 7, 2021 at 13:58
• @Hanno I assume that all eigenvalues are outside of unit disk. So in general, magnitude of complex eigenvalue larger than $1$, but if we want to simplify, it is ok to assume that all eigenvalues are real and larger than 1.
– Lee
May 7, 2021 at 15:24
• @Balajisb : I think there must be a minus sign in $A^TA - A^T(I+X)^{-1}A$. May 8, 2021 at 19:24

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

1. 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)}$$

• here you are assuming that $A$ is diagonalizable, I have included solution for that case. I am looking for a solution when $A$ is not diagonalizable. For example: $A=\begin{bmatrix} 2 & 1 \\ &2 \end{bmatrix}$
– Lee
May 9, 2021 at 4:07
• Look at point 1) in the edited answer in "Proceeding with assumptions". You can use that probably to get tight bounds. In point 1) i have assumed only $A^TA$ is diagonalizable May 9, 2021 at 4:11
• I have tested results in part 1, it doesn't hold. For $A=\begin{bmatrix} 2&1\\ &2 \end{bmatrix}$, $X=\begin{bmatrix} 2.7&1.8 \\ 1.8&4.2 \end{bmatrix}$. $\mathrm{eig}((A^TA)^{-1})=[0.1524\quad 0.4101]$, $\mathrm{eig}(X)=[1.5\quad 5.4]$. So the first question is which eigenvalue of $(A^TA)^{-1}$ must be paired with which eigenvalue of $X$? I guess, the largest with largest. Then LHS$=2.4431>1.4438=$RHS. If we change the pairing LHS$=1.4381<1.4438=$RHS. I have used the following equation $\sum_i \lambda_i((A^TA)^{-1}) \lambda_i(X) = n-\sum_i \frac{1}{1+\lambda_i(X)}$
– Lee
May 9, 2021 at 4:26
• @Lee As stated in my answer, u need to satisfy the assumptions that $A^TA$ and $X+X^T$ is simultaneously diagonalizable then only the equation in point 1) will hold. May 9, 2021 at 4:27
• +1 thanks for the attempt
– Lee
May 9, 2021 at 4:32

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

• For $A=\begin{bmatrix} 2&1 \\ 0&2 \end{bmatrix}$, $X=\begin{bmatrix} 2.7&1.8 \\ 1.8&4,2 \end{bmatrix}$ satisfies $X=A^TX(I+X)^{-1}A$, so $\mathrm{Tr}(X)=6.9$, while $\mathrm{Tr}(AA^T)-n=7$. The difference not big, but still there is a gap
– Lee
May 5, 2021 at 10:21
• I also got this: For $A=\begin{bmatrix} 2&1 \\ 0&2 \end{bmatrix}$, $U=\begin{bmatrix} 0.6154&-0.7882 \\ -0.7882&-0.6154 \end{bmatrix}$ and $\Sigma=\mathrm{diag}(2.4384,6.5616)$, then $Y=U(\Sigma-I)U^T=\begin{bmatrix} 4&2 \\ 2&3 \end{bmatrix}$, while $A^T Y(I+Y)^{-1}A=\begin{bmatrix} 3&2 \\ 2&4 \end{bmatrix}$, thus $Y\neq A^T Y(I+Y)^{-1}A$.
– Lee
May 5, 2021 at 11:12
• $A^T Y(I+Y)^{-1}A=A^TIA-A^T(AA^T)^{-1}A=A^TA-I\neq AA^T-I=Y^T=Y$ looks like the second last equality doesn't hold. Thank you very much for your answer, it gave me some understanding +1
– Lee
May 5, 2021 at 11:29
• Thank you for catching that, I leave the answer in case someone find it useful in some way, even though it is unlikely. May 5, 2021 at 13:59

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