4
$\begingroup$

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)] );
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Semiclassical Aug 14 at 21:48
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – Semiclassical Aug 12 at 18:04
  • $\begingroup$ 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. $\endgroup$ – kx526 Aug 13 at 0:18
  • $\begingroup$ 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$. $\endgroup$ – kx526 Aug 13 at 0:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Semiclassical Aug 13 at 1:24
  • $\begingroup$ 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... $\endgroup$ – kx526 Aug 13 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.