Showing $\det\big[ (B+K)^{-1} (A+K) \big] = O(1)$ when $A,B$ are rank 1 updates of $I_n$ and $K$ is symmetric PD with positive entries - Mathematics Stack Exchange most recent 30 from math.stackexchange.com 2019-12-05T17:48:24Z https://math.stackexchange.com/feeds/question/3318386 https://creativecommons.org/licenses/by-sa/4.0/rdf https://math.stackexchange.com/q/3318386 4 Showing $\det\big[ (B+K)^{-1} (A+K) \big] = O(1)$ when $A,B$ are rank 1 updates of $I_n$ and $K$ is symmetric PD with positive entries kx526 https://math.stackexchange.com/users/646406 2019-08-09T15:36:48Z 2019-08-15T16:21:35Z <p>In general, given <span class="math-container">$n$</span> define <span class="math-container">$m_A, m_B \in\{1,...,n-1\}$</span> by <span class="math-container">$$m_A = floor(a \times n)$$</span> <span class="math-container">$$m_B = floor(b \times n )$$</span> where the constants <span class="math-container">$a,b \in (0,1)$</span> are independent of <span class="math-container">$n$</span> with <span class="math-container">$a \ne b$</span> .</p> <p>Define two matrices as rank 1 updates of the identity matrix:</p> <p><span class="math-container">$$A=I_n +u_A u_A^\top\; \text{where}\; (u_A)_i=\left\{\begin{array}{cc} 0, &amp; i\leq n-m_A \\ 1 &amp; \text{else} \end{array}\right.,$$</span> <span class="math-container">$$B=I_n +u_B u_B^\top\; \text{where}\; (u_B)_i=\left\{\begin{array}{cc} 0, &amp; i\leq n-m_B \\ 1 &amp; \text{else} \end{array}\right.$$</span> or equivalently, <span class="math-container">\begin{equation} A = \begin{pmatrix} I_{n-m_A} &amp; 0 \\ 0 &amp; I_{m_A} + J_{m_A} \\ \end{pmatrix}, B = \begin{pmatrix} I_{n-m_B} &amp; 0 \\ 0 &amp; I_{m_B} + J_{m_B} \\ \end{pmatrix}, \end{equation}</span> where <span class="math-container">$J_m$</span> is a <span class="math-container">$m \times m$</span> matrix of ones. </p> <p><strong>My goal</strong></p> <p>Now, let <span class="math-container">$K$</span> be a <span class="math-container">$n \times n$</span> symmetric positive definite matrix with positive entries. My goal is to show that <span class="math-container">$\det\left[ (B+K)^{-1} (A+K) \right]$</span> is <span class="math-container">$O(1)$</span> as <span class="math-container">$n \to \infty$</span>. Hence, I would like to find bounds which are <span class="math-container">$O(1)$</span>. </p> <p><strong>Findings so far</strong></p> <ul> <li><p>From <a href="https://math.stackexchange.com/a/3313801/646406">link1</a>, I know that 1 as an eigenvalue of the matrix <span class="math-container">$B^{-1}A$</span> has multiplicity <span class="math-container">$n-2$</span>. From <a href="https://math.stackexchange.com/a/3317449/646406">link2</a>, I also know that <span class="math-container">$\det(B^{-1}A) =\frac{m_A+1}{m_B+1}$</span> and <span class="math-container">$\det(A^{-1}B) =\frac{m_B+1}{m_A+1}$</span>.</p></li> <li><p>Thank to the suggestion (<a href="https://math.stackexchange.com/a/3321218/646406">link3</a>) by @Semiclassical, <span class="math-container">$$\det[(B+K)^{-1})(A+K)] =\frac{\det(A+K)}{\det(B+K)} =\frac{\det(K+I_n+u_A u_A^\top)}{\det(K+I_n+u_B u_B^\top)} =\frac{(1+u_A^\top(K+I_n)^{-1} u_A)\det(K+I_n)}{(1+u_B^\top(K+I_n)^{-1} u_B)\det(K+I_n)}=\frac{1+u_A^\top(K+I_n)^{-1} u_A}{1+u_B^\top(K+I_n)^{-1} u_B}$$</span> where the third equality holds due to the identity <span class="math-container">$\det(X+uv^\top)=(1+u^\top X^{-1}v)\det X$</span>.</p></li> </ul> <p><strong>My attempts and Questions</strong></p> <p><strong>(Question 1)</strong></p> <p>Through numerical experiments in Matlab, I found candidate bounds that seem to work for various versions of <span class="math-container">$K$</span> (the Matlab code can be found below). So my question is: is the following statement true for all <span class="math-container">$n$</span> and <span class="math-container">$K$</span> (any symmetric positive definite matrix with only positive entries)?</p> <p>I. If <span class="math-container">$m_B&lt;m_A$</span>, then <span class="math-container">\begin{align*} \det (A^{-1}B) \leq \det\left[ (B+K)^{-1} (A+K) \right] \leq \det (B^{-1}A) \end{align*}</span> II. If <span class="math-container">$m_B&gt;m_A$</span>, then <span class="math-container">\begin{align*} \det (B^{-1}A) \leq \det\left[ (B+K)^{-1} (A+K) \right] \leq \det (A^{-1}B) \end{align*}</span> or equivalently, </p> <p>I. If <span class="math-container">$m_B&lt;m_A$</span>, then <span class="math-container">\begin{align*} \frac{1+m_B}{1+m_A} \leq \frac{1+u_A^\top(K+I_n)^{-1} u_A}{1+u_B^\top(K+I_n)^{-1} u_B} \leq \frac{1+m_A}{1+m_B} \end{align*}</span> II. If <span class="math-container">$m_B&gt;m_A$</span>, then <span class="math-container">\begin{align*} \frac{1+m_A}{1+m_B} \leq \frac{1+u_A^\top(K+I_n)^{-1} u_A}{1+u_B^\top(K+I_n)^{-1} u_B} \leq \frac{1+m_B}{1+m_A} \end{align*}</span></p> <p>where <span class="math-container">$\frac{1+m_A}{1+m_B}\approx \frac{1+a\times n}{1+b \times n}=\frac{1/n + a}{1/n +b}$</span> and <span class="math-container">$\frac{1+m_B}{1+m_A} \approx \frac{1/n+b}{1/n+a}$</span> are <span class="math-container">$O(1)$</span>, so the inequalities would imply that <span class="math-container">$\det\left[ (B+K)^{-1} (A+K) \right]=O(1)$</span> which is my goal.</p> <p><strong>(Question 2)</strong></p> <p>Are there any other bounds for <span class="math-container">$\det\left[ (B+K)^{-1} (A+K) \right]$</span> that are <span class="math-container">$O(1)$</span> (possibly obvious bounds that I am missing)?</p> <p><strong>Note</strong></p> <p>I initially thought a sharper bound by <span class="math-container">$1$</span> might be possible, but it was not. Suppose <span class="math-container">$m_B&lt;m_A$</span>. It is not guaranteed that <span class="math-container">$u_A^T(K+I_n)^{-1}u_A -u_B^T(K+I_n)^{-1}u_B \geq 0$</span>. To see this, for instance, consider the example provided <a href="https://math.stackexchange.com/a/3321792/646406">here</a> with the matrix <span class="math-container">$$K = \begin{bmatrix} 1 &amp; 1 &amp; 1\\ 1 &amp; 100 &amp; 99\\ 1 &amp; 99 &amp; 100\\ \end{bmatrix}, \\$$</span> and the vectors <span class="math-container">$u_A = (0, 1, 1)$</span> and <span class="math-container">$u_B =(0, 0, 1)$</span>.</p> <p>This means that the sharper lower bound by <span class="math-container">$1$</span>: <span class="math-container">\begin{align*} \frac{1+m_B}{1+m_A} &lt; 1 \leq \frac{1+u_A^T(K+I_n)^{-1}u_A}{1+u_B^T(K+I_n)^{-1}u_B} \end{align*}</span> is not possible. However, the proposed bounds by <span class="math-container">$\frac{1+m_B}{1+m_A}$</span> and <span class="math-container">$\frac{1+m_A}{1+m_B}$</span> still work even with the <span class="math-container">$K$</span>, <span class="math-container">$u_A$</span>, and <span class="math-container">$u_B$</span> in the example above.</p> <p><strong>Code</strong></p> <p>Matlab code for a fixed <span class="math-container">$n$</span>:</p> <pre><code>% 1. Specify n,a,b n=5; a=0.7;b=0.3; mA=floor(a*n); mB=floor(b*n); % 2. Define matrices A and B % Define a vector uA whose first n-mA entries = 0 and the last mA entries =1 uA=ones(n,1);uA(1:n-mA)=0; A=eye(n)+uA*uA'; % Do the same for B uB=ones(n,1);uB(1:n-mB)=0; B=eye(n)+uB*uB'; % 3. Define a (this can be any) symmetric PD matrix K with positive entires K = rand(n,n);K = 0.5*(K+K'); K = K + n*eye(n); % 4. Check that det(A) = m_A +1. Same for B. det(A) mA+1 det(B) mB+1 % 5. Compare three items (mB+1)/(mA+1) det(inv(B+K)*(A+K)) (mA+1)/(mB+1) </code></pre> <p>Matlab code for varying <span class="math-container">$n$</span>:</p> <pre><code>n_grid=10:100:1000; a=0.7;b=0.3; for i=1:length(n_grid) n=n_grid(i); mA=floor(a*n); mB=floor(b*n); uA=ones(n,1);uA(1:n-mA)=0; A=eye(n)+uA*uA'; uB=ones(n,1);uB(1:n-mB)=0; B=eye(n)+uB*uB'; K = rand(n,n);K = 0.5*(K+K'); K = K + n*eye(n); determinant(i) = det(inv(B+K)*(A+K)); det_invBA(i)=(mA+1)/(mB+1); % determinant of inv(B)*A det_invAB(i)=(mB+1)/(mA+1); % determinant of inv(A)*B end figure plot(n_grid,determinant,'*');xlabel('n'); hold on plot(n_grid,det_invBA,'*'); hold on plot(n_grid,det_invAB,'*'); legend('det (B+K)^{-1}(A+K)','det B^{-1}A','det A^{-1}B'); xlim([n_grid(1),n_grid(end)]);xlabel('n') title(['a =',num2str(a),' b =',num2str(b)] ); </code></pre> https://math.stackexchange.com/questions/3318386/showing-det-big-bk-1-ak-big-o1-when-a-b-are-rank-1-updates/3321218#3321218 2 Answer by Semiclassical for Showing $\det\big[ (B+K)^{-1} (A+K) \big] = O(1)$ when $A,B$ are rank 1 updates of $I_n$ and $K$ is symmetric PD with positive entries Semiclassical https://math.stackexchange.com/users/137524 2019-08-12T16:50:22Z 2019-08-12T17:13:36Z <p>I can't provide a proof either, but the following formula may be helpful. First, for convenience I'll rewrite <span class="math-container">$A,B$</span> as rank-one updates of the identity matrix: <span class="math-container">$$A=I_n +u_A u_A^\top\; \text{where}\; (u_A)_i=\left\{\begin{array}{cc} 0, &amp; i\leq n-m_A \\ 1 &amp; \text{else} \end{array}\right.,$$</span> <span class="math-container">$$B=I_n +u_B u_B^\top\; \text{where}\; (u_B)_i=\left\{\begin{array}{cc} 0, &amp; i\leq n-m_B \\ 1 &amp; \text{else} \end{array}\right.$$</span> In these forms it is particularly obvious that <span class="math-container">$A$</span> has eigenvalue <span class="math-container">$1+m_A$</span> with multiplicity (eigenvector <span class="math-container">$u_A$</span>) and eigenvalue <span class="math-container">$1$</span> with multiplicity <span class="math-container">$n-1$</span> (<span class="math-container">$n-1$</span> eigenvectors perpendicular to <span class="math-container">$u_A$</span>); a similar description works for <span class="math-container">$B$</span>.</p> <p>The main advantage, however, is that we may write the expression to be bounded as <span class="math-container">$$\det[(B+K)^{-1})(A+K)] =\frac{\det(A+K)}{\det(B+K)} =\frac{\det(K+I_n+u_A u_A^\top)}{\det(K+I_n+u_B u_B^\top)}.$$</span> We can now apply the matrix determinant lemma <span class="math-container">$\det(A+uv^\top)=(1+u^\top A^{-1}v)\det A$</span>, obtaining</p> <p><span class="math-container">$$\frac{\det(K+I_n+u_A u_A^\top)}{\det(K+I_n+u_B u_B^\top)}=\frac{(1+u_A^\top(K+I_n)^{-1} u_A)\det(K+I_n)}{(1+u_B^\top(K+I_n)^{-1} u_B)\det(K+I_n)}=\frac{1+u_A^\top(K+I_n)^{-1} u_A}{1+u_B^\top(K+I_n)^{-1} u_B}.$$</span> As a check on this formula, note that we have not yet used any properties of <span class="math-container">$K$</span>. Hence it is legitimate to replace <span class="math-container">$K\to 0$</span> to get <span class="math-container">$$\det(B^{-1}A)=\frac{1+u_A^\top(I_n)^{-1} u_A}{1+u_B^\top(I_n)^{-1} u_B}=\frac{1+u_A^\top u_A}{1+u_B^\top u_B}=\frac{1+m_A}{1+m_B}$$</span> as obtained in the linked problem. </p> <p>In this form, the inequality to be proven (in the case <span class="math-container">$m_B&lt;m_A$</span>) is <span class="math-container">$$\frac{1+m_B}{1+m_A}\leq \frac{1+u_A^\top(K+I_n)^{-1} u_A}{1+u_B^\top(K+I_n)^{-1} u_B}\leq \frac{1+m_A}{1+m_B}.$$</span> Alas, I'm not sure how to proceed from here. One could appeal to the spectral theorem to write the eigendecomposition of <span class="math-container">$K$</span>, but this seems to lead back to the expression in the problem statement. Other decompositions of positive definite <span class="math-container">$K$</span> which may be useful are the Cholesky decomposition or the related LDLT decomposition. The <a href="https://en.wikipedia.org/wiki/Woodbury_matrix_identity" rel="nofollow noreferrer">Woodbury matrix identity</a> may also be useful in handling the inverse. Finally, the fact that <span class="math-container">$K$</span> has positive entries may make it useful to explore the Perron-Frobenius theorem.</p>