This question is a continuation of Bounding the norm of an inverse matrix from above.
Let $d_1>d_2>\dots>d_N>1$, and let $D_{s}:=Diag(d_1,…,d_s)$ and $D_k=Diag(d_{s+1},…,d_N)$. In addition, let $X$ be an integer matrix of size $(N-s)\times s$. I am interested in the matrix $B:=Id_{s}+D_{s}^{-1}X^{t}D_{k}X$, in particular, I am interested in bounding the norm $||B^{-1}||$ from above.
From the discussion in the attached post, we know that $B$ is similar to $B’:=Id_{s}+D_{s}^{-1/2}X^{t}D_{k}XD^{-1/2}_{s}$, and $B’$ Is positive definite whose eigenvalues are larger than $1$ since $B’\geq Id_{s}$. Thus $||(B’)^{-1}||<1$. However, since $B$ itself is not positive definite, we don’t really learn a lot about $||B^{-1}||$.
I am convinced that $||B^{-1}||<poly(N)$, i.e there is a polynomial in $N$ that bounds this norm. However, I am not able to prove this, I am only able to prove that $||B^{-1}||<poly(e^N,e^{M})$, where $||X||<M$. For my purposes, it is enough to achieve $||B^{-1}||<poly(M,N)$.
The way I bound $B^{-1}$ is just literally computing it. It is not hard to see from say cauchy binet formula that $Det(B)>d_{1}\cdot\dots\cdot d_{s}$, and when computing entries of $Adj(B)$, we will have sums of products of $s$ $d’s$ with some minors of $X$. Thus I can bound the entries of $B^{-1}$ from above, but I will have too many summands (N choose s approx.), and I use $||X||$, which is taken to the power $N$ in the worst case. I don’t use the fact that $Det(B)$ itself also have such summands, just the above mentioned inequality.
Any hints or ideas about bounding $||B^{-1}||$ from above elegantly will be really aprecciated! I’m sure there must be a way, I even conjecture that in fact, $||B^{-1}||<1$, but again, $poly(N,||X||)$ is the bound I’m really looking for.
Thank you very much!
Ok, I think I solved it. Consider the following Identity. $(Id+D_{s}^{-1}X^{t}D_{k}X)^{-1}=Id-D^{-1}_{s}X^t(D_{k}^{-1}+XD_{s}^{-1}X^{t})^{-1}X$.
Thus $||B^{-1}||\leq 1+\frac{d_{s+1}}{d_{s}}||X||^{2}\leq1+||X||^{2}$, as I wanted.