13

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

Lee
  • 1,910
  • 12
  • 19
  • 3
    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. – Paul Sinclair May 01 '21 at 16:19
  • 1
    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. – Balaji sb May 05 '21 at 14:30
  • 1
    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$"? – Hanno May 07 '21 at 13:58
  • 1
    @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 07 '21 at 15:24
  • 2
    @Balajisb : I think there must be a minus sign in $A^TA - A^T(I+X)^{-1}A$. – Han de Bruijn May 08 '21 at 19:24
  • Anyway it follows that $,\det(I+X)=\det(A)^2,$. – Han de Bruijn May 08 '21 at 19:34
  • @HandeBruijn yes, I found that $\mathrm{det}(I+X)=\mathrm{det}(A)^2$, however it only helps to find some lower bound that is not always achievable. – Lee May 09 '21 at 03:50
  • Series expansion $,X=A^TXA-A^TX^2A+A^TX^3A-A^TX^4A+A^TX^5A+\cdots$ , with certain restrictions on $X$. And the trace of a sum is the sum of the traces. That's no answer yet, I know. – Han de Bruijn May 09 '21 at 11:32
  • $\mathrm{det}(I+X)=\mathrm{det}(A)^2$ has helped me to find a solution with general $2\times 2$ matrix $A$ and MAPLE. I find it not very instructive, though. Curious? – Han de Bruijn May 11 '21 at 12:31
  • @HandeBruijn I have also solved general $2\times 2$ case. But you can share anyway, your answer might be useful for us to learn – Lee May 11 '21 at 12:37
  • Avoiding answering in comments, I''ve formulated an answer for the $2\times 2$ case only. – Han de Bruijn May 12 '21 at 07:19

3 Answers3

3

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

P. Quinton
  • 6,031
  • 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 05 '21 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 05 '21 at 11:12
  • 1
    $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 05 '21 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. – P. Quinton May 05 '21 at 13:59
3

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

Balaji sb
  • 4,357
  • 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 09 '21 at 04: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 – Balaji sb May 09 '21 at 04: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 09 '21 at 04: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. – Balaji sb May 09 '21 at 04:27
  • +1 thanks for the attempt – Lee May 09 '21 at 04:32
  • @Lee I have added a bound in my answer without assumptions. See if this is useful. – Balaji sb May 09 '21 at 04:53
1

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

Han de Bruijn
  • 17,070