5

Assume that $A \in \mathbb{R}^{N \times N}$ is a positive semi-definite matrix, both $\|A\|_1$ and $\|A^{-1}\|_1$ are uniformly bounded as $N \to \infty.$ Here $\| \cdot \|_1$ is the induced $L_1$ Norm. Prove that there exists a constant $\kappa > 0$ such that $$\|(I_N+A)^{-1}\|_1 \leq \kappa $$ as $N \to \infty.$ Else show a counterexample.

I attempted to demonstrate that the boundedness of $\|(I_N+A)^{-1}\|_1$ can be proven using the definition of $\| \cdot \|_1$ as follows

$$ \|(I_N + A)^{-1} \|_1 = \sup_{x \neq 0} \frac{ \|(I_N + A)^{-1} x\|_1 }{\|x\|_1} = \sup_{z \neq 0} \frac{ \|z\|_1 }{\|(I_N+A)z\|_1} \leq \sup_{z \neq 0} \frac{ \|z\|_1 }{|\|Az\|_1 - \|z\|_1|} = \sup_{z \neq 0} \frac{1}{ \Big| \frac{\|Az\|_1}{\|z\|_1} - 1 \Big| } $$

However, it seems possible that $\inf_{z} \Big|\frac{\|Az\|_1}{\|z\|_1} - 1 \Big|=0$, so I doubt this proof is wrong.

But intuitively, $(I_N + A)^{-1}$ seems to be smaller than $A^{-1}$, and when we consider $L_2$ norm, it is easy to find that $\|(I_N + A)^{-1}\|_2 \leq 1$, so I guess the boundedness still holds when we consider $L_1$ norm.

Any guidance on how to tackle this problem? Thanks a ton!

Golden Silence
  • 51
  • Hint: what do the conditions say about the eigenvalues of $A$ and what are the eigenvalues of $I_N + A$. – V.S.e.H. Apr 09 '23 at 12:00
  • Sorry, could you please explain it a bit more clearly? – Golden Silence Apr 09 '23 at 14:51
  • Your matrix is Hermitian, right? Then you can decompose it via $A = UDU^$, where $U$ is unitary. Notice that $|U|_1 \leq 1$ and $|U^|_1 \leq 1$, so in the end you just need to bound the eigenvalues of $(I + A)^{-1}$. But, please clarify if $A$ is Hermitian. – V.S.e.H. Apr 09 '23 at 15:56
  • @V.S.e.H. Yes, but I think the unitary matrix $U$ could have a large L1 norm. For example, consider setting the first column of $U$ to be $N^{-1/2}*(1, 1, ..., 1)$, then the column sum is $\sqrt{N}$ – Golden Silence Apr 10 '23 at 01:57
  • Ah, good point. I completely overlooked that. Still, if one can show that the 1-norms of these matrices are uniformly bounded, then the problem is solved. – V.S.e.H. Apr 10 '23 at 10:14
  • 1
    Define $A_N \in \mathbb{R}^{N \times N}$ to be ${(A_N)}_{ij} =
    \begin{cases} -1 + \frac{1}{N} \text{ if i = j}\ 0 \text{ i \neq j} \end{cases}$,

    It follows that ${A_N}^{-1}=
    \begin{cases} \frac{N}{1-N} \text{ if i = j}\ 0 \text{ if } i \neq j \end{cases}$

    If I'm not mistaken, both $\left|\left|A_N \right|\right|_1 \text{ and } \left|\left|{A_N}^{-1} \right|\right|_1\leq \frac{N} {N -1} \text{, but} \left|\left| (1 + A_N)^{-1} \right|\right|_1 \ge N$

     – Catriel Apr 10 '23 at 14:06
  • 1
    @Catriel $A_N$ is not positive definite then. – V.S.e.H. Apr 10 '23 at 15:11
  • Sorry about that! – Catriel Apr 10 '23 at 15:14
  • The answer below seems correct ? – Balaji sb Apr 11 '23 at 05:16

1 Answers1

2

$$||(I+A^{-1})||$$ is finite iff $$\inf_{z:||z||_1 = 1} ||(I+A)z||_1 > 0.$$ Suppose not, $(I+A)z_n \rightarrow 0 \implies ||(I+A)z_n||_1 \leq \epsilon_N \implies Az_n = -z_n + v_{\epsilon_N}$ implies $z_n^TAz_n < 0$ for all $n \geq M$, where $||v_{\epsilon_N}||_1<\epsilon_N$ a contradiction to positive definiteness. Hence $$\inf_{z:||z||_1 = 1} ||(I+A)z||_1 = \epsilon_N/2.$$ for some $\epsilon_N>0$. Suppose $\epsilon_N \rightarrow 0$ as $N \rightarrow \infty$ then for the contradction to fail you must have, $$Az_n = -z_n + v_{\epsilon_N}$$ with $||z_n||_2 < ||v_{\epsilon_N}||_2 < ||v_{\epsilon_N}||_1 < \epsilon_N$.

Hence $$z_n^TAz_n = -||z_n||_2^2+<z_n,v_{\epsilon_N}>$$ $$\frac{z_n^TAz_n}{||z_n||_2^2} = -1+\frac{<z_n,v_{\epsilon_N}>}{||z_n||_2^2}$$ $$\frac{z_n^TAz_n}{||z_n||_2^2} \leq -1+\frac{||v_{\epsilon_N}||_2}{||z_n||_2}$$ $$\frac{z_n^TAz_n}{||z_n||_2^2} \leq -1+\frac{\epsilon_N}{||z_n||_2}$$ $$\lambda_{\min}(A) \leq -1+\frac{2}{||z_n||_2 ||(I+A)^{-1}||_1}$$ From above derivation constant $2$ can be reduced and be made $1$ and and we get $$\lambda_{\min}(A) \leq -1+\frac{1}{||z_n||_2 ||(I+A)^{-1}||_1}$$

Hence, $$\frac{1}{||z_n||_2 ||(I+A)^{-1}||_1} \geq 1$$ $$||z_n||_2 ||(I+A)^{-1}||_1 \leq 1.$$ $$||z^*||_2 ||(I+A)^{-1}||_1 \leq 1.$$ where $z^*$ achieves $\inf_{z:||z||_1 = 1} ||(I+A)z||_1$ and $||z^*||_1 = 1$. Now $z^* = (I+A)^{-1}x^*$ where $x^*$ achieves $||(I+A)^{-1}||_1$ and it can be chosen as $x^* = [0,...1,0,...0]$ with $1$ at column of $(I+A)^{-1}$ with max $L_1$ norm. Let $x^* = e_j$ with $1$ at $j^{th}$ position. Hence $$||(I+A)^{-1}x^*||_2 ||(I+A)^{-1}||_1 \leq 1.$$ $$||(I+A)^{-1}e_j||_2 ||(I+A)^{-1}||_1 \leq 1.$$ $$\lambda_{\min}((I+A)^{-1}) ||(I+A)^{-1}||_1 \leq 1.$$ $$\frac{1}{\lambda_{\max}((I+A))} ||(I+A)^{-1}||_1 \leq 1.$$ $$ ||(I+A)^{-1}||_1 \leq \lambda_{\max}((I+A)).$$ Hence uniformly bounded. Hence proved.

Balaji sb
  • 4,357