13
$\begingroup$

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

$\endgroup$
11
  • 3
    $\begingroup$ 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. $\endgroup$ May 1, 2021 at 16:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Balaji sb
    May 5, 2021 at 14:30
  • 1
    $\begingroup$ 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$"? $\endgroup$
    – Hanno
    May 7, 2021 at 13:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – Lee
    May 7, 2021 at 15:24
  • 2
    $\begingroup$ @Balajisb : I think there must be a minus sign in $A^TA - A^T(I+X)^{-1}A$. $\endgroup$ May 8, 2021 at 19:24

3 Answers 3

3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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}$ $\endgroup$
    – Lee
    May 9, 2021 at 4:07
  • $\begingroup$ 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 $\endgroup$
    – Balaji sb
    May 9, 2021 at 4:11
  • $\begingroup$ 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)}$ $\endgroup$
    – Lee
    May 9, 2021 at 4:26
  • $\begingroup$ @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. $\endgroup$
    – Balaji sb
    May 9, 2021 at 4:27
  • $\begingroup$ +1 thanks for the attempt $\endgroup$
    – Lee
    May 9, 2021 at 4:32
3
+25
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – Lee
    May 5, 2021 at 10:21
  • $\begingroup$ 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$. $\endgroup$
    – Lee
    May 5, 2021 at 11:12
  • 1
    $\begingroup$ $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 $\endgroup$
    – Lee
    May 5, 2021 at 11:29
  • $\begingroup$ Thank you for catching that, I leave the answer in case someone find it useful in some way, even though it is unlikely. $\endgroup$
    – P. Quinton
    May 5, 2021 at 13:59
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.