# 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, 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, 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. 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 think I may have found some counterexamples for both upper and lower bounds. Thus far they're numerical, though, and involve fairly large matrices (dimension at least 6). I'll see if I can find more natural counterexamples. – Semiclassical Aug 14 at 21:48

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

• Based on some numerical checks of my own, it appears that $u_A^\top (K+I_n)^{-1} u_A > u_B^\top (K+I_n)^{-1} u_B$ when $m_A>m_B$. (This is plausible to me on the grounds that $u_A-u_B$ is a non-negative vector.) If so, then one may sharpen the lower bound to $$\det(A^{-1}B)\leq 1 < \det[(B+K)^{-1}(A+K)].$$ This still leaves the upper bound... – Semiclassical Aug 12 at 18:04
• Thank you for the suggestions! Your formulation seems to be more natural than mine, so I edited my question accordingly. I also think it seems like 1 is a lower bound if $𝑚_𝐵<𝑚_𝐴$ and it is an upper bound if $𝑚_𝐵>𝑚_𝐴$, but I has not been able to prove it. – kx526 Aug 13 at 0:18
• If $(K+I_n)^{-1}$ were a matrix with only positive entries, the fact that $u_A-u_B$ is a non-negative vector implies that $u_A^T(K+I_n)^{-1}u_A - u_B^T(K+I_n)^{-1}u_B \geq 0$. Here, $(K+I_n)^{-1}$ can have negative entries although we know that it is symmetric positive definite and hence its eigenvalues are positive. The post shows that we need not have $u_A^T(K+I_n)^{-1}u_A - u_B^T(K+I_n)^{-1}u_B \geq 0$. – kx526 Aug 13 at 0:45
• I agree that $K$ being positive definite isn't enough by itself. But we also know that $K$ has positive entries, and that's why I thought the sharper bound was plausible. But absent an actual proof, it remains a conjecture. – Semiclassical Aug 13 at 1:24
• As shown here, $K$ being symmetric positive definite with positive entries and $m_B<m_A$ do not imply that $u_A^T(K+I_n)^{-1}u_A-u_B^T(K+I_n)^{-1}u_B \geq 0$. However, $$\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}$$ still holds even when I let $K=M$ where $M$ is the example matrix given in the previously mentioned post... – kx526 Aug 13 at 14:49