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

In general, given $n$ define $m_A, m_B \in\{1,...,n-1\}$ by $$ m_A = floor(a \times n) $$ $$ m_B = floor(b \times n ) $$ where the constants $a,b \in (0,1)$ are independent of $n$ with $a \ne b$ .

Define two matrices as rank 1 updates of the identity matrix:

$$A=I_n +u_A u_A^\top\; \text{where}\; (u_A)_i=\left\{\begin{array}{cc} 0, & i\leq n-m_A \\ 1 & \text{else} \end{array}\right.,$$ $$B=I_n +u_B u_B^\top\; \text{where}\; (u_B)_i=\left\{\begin{array}{cc} 0, & i\leq n-m_B \\ 1 & \text{else} \end{array}\right.$$ or equivalently, \begin{equation} A = \begin{pmatrix} I_{n-m_A} & 0 \\ 0 & I_{m_A} + J_{m_A} \\ \end{pmatrix}, B = \begin{pmatrix} I_{n-m_B} & 0 \\ 0 & I_{m_B} + J_{m_B} \\ \end{pmatrix}, \end{equation} where $J_m$ is a $m \times m$ matrix of ones.

My goal

Now, let $K$ be a $n \times n$ symmetric positive definite matrix with positive entries. My goal is to show that $\det\left[ (B+K)^{-1} (A+K) \right]$ is $O(1)$ as $n \to \infty$. Hence, I would like to find bounds which are $O(1)$.

Findings so far

• From link1, I know that 1 as an eigenvalue of the matrix $B^{-1}A$ has multiplicity $n-2$. From link2, I also know that $\det(B^{-1}A) =\frac{m_A+1}{m_B+1}$ and $\det(A^{-1}B) =\frac{m_B+1}{m_A+1}$.

• Thank to the suggestion (link3) by @Semiclassical, $$\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}$$ where the third equality holds due to the identity $\det(X+uv^\top)=(1+u^\top X^{-1}v)\det X$.

My attempts and Questions

(Question 1)

Through numerical experiments in Matlab, I found candidate bounds that seem to work for various versions of $K$ (the Matlab code can be found below). So my question is: is the following statement true for all $n$ and $K$ (any symmetric positive definite matrix with only positive entries)?

I. If $m_B<m_A$, then \begin{align*} \det (A^{-1}B) \leq \det\left[ (B+K)^{-1} (A+K) \right] \leq \det (B^{-1}A) \end{align*} II. If $m_B>m_A$, then \begin{align*} \det (B^{-1}A) \leq \det\left[ (B+K)^{-1} (A+K) \right] \leq \det (A^{-1}B) \end{align*} or equivalently,

I. If $m_B<m_A$, then \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*} II. If $m_B>m_A$, then \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*}

where $\frac{1+m_A}{1+m_B}\approx \frac{1+a\times n}{1+b \times n}=\frac{1/n + a}{1/n +b}$ and $\frac{1+m_B}{1+m_A} \approx \frac{1/n+b}{1/n+a}$ are $O(1)$, so the inequalities would imply that $\det\left[ (B+K)^{-1} (A+K) \right]=O(1)$ which is my goal.

(Question 2)

Are there any other bounds for $\det\left[ (B+K)^{-1} (A+K) \right]$ that are $O(1)$ (possibly obvious bounds that I am missing)?

Note

I initially thought a sharper bound by $1$ might be possible, but it was not. Suppose $m_B<m_A$. It is not guaranteed that $u_A^T(K+I_n)^{-1}u_A -u_B^T(K+I_n)^{-1}u_B \geq 0$. To see this, for instance, consider the example provided here with the matrix $$K = \begin{bmatrix} 1 & 1 & 1\\ 1 & 100 & 99\\ 1 & 99 & 100\\ \end{bmatrix}, \\ $$ and the vectors $u_A = (0, 1, 1)$ and $u_B =(0, 0, 1)$.

This means that the sharper lower bound by $1$: \begin{align*} \frac{1+m_B}{1+m_A} < 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*} is not possible. However, the proposed bounds by $\frac{1+m_B}{1+m_A}$ and $\frac{1+m_A}{1+m_B}$ still work even with the $K$, $u_A$, and $u_B$ in the example above.

Code

Matlab code for a fixed $n$:

% 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)

Matlab code for varying $n$:

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)] );

I can't provide a proof either, but the following formula may be helpful. First, for convenience I'll rewrite $A,B$ as rank-one updates of the identity matrix: $$A=I_n +u_A u_A^\top\; \text{where}\; (u_A)_i=\left\{\begin{array}{cc} 0, & i\leq n-m_A \\ 1 & \text{else} \end{array}\right.,$$ $$B=I_n +u_B u_B^\top\; \text{where}\; (u_B)_i=\left\{\begin{array}{cc} 0, & i\leq n-m_B \\ 1 & \text{else} \end{array}\right.$$ In these forms it is particularly obvious that $A$ has eigenvalue $1+m_A$ with multiplicity (eigenvector $u_A$) and eigenvalue $1$ with multiplicity $n-1$ ($n-1$ eigenvectors perpendicular to $u_A$); a similar description works for $B$.

The main advantage, however, is that we may write the expression to be bounded as $$\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)}. $$ We can now apply the matrix determinant lemma $\det(A+uv^\top)=(1+u^\top A^{-1}v)\det A$, obtaining

$$\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}.$$ As a check on this formula, note that we have not yet used any properties of $K$. Hence it is legitimate to replace $K\to 0$ to get $$\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}$$ as obtained in the linked problem.

In this form, the inequality to be proven (in the case $m_B<m_A$) is $$\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}.$$ Alas, I'm not sure how to proceed from here. One could appeal to the spectral theorem to write the eigendecomposition of $K$, but this seems to lead back to the expression in the problem statement. Other decompositions of positive definite $K$ which may be useful are the Cholesky decomposition or the related LDLT decomposition. The Woodbury matrix identity may also be useful in handling the inverse. Finally, the fact that $K$ has positive entries may make it useful to explore the Perron-Frobenius theorem.