2
$\begingroup$

Suppose $A$ is a symmetric positive definite matrix of $n \times n$ dimensions. Matrix $B \in \mathbb{R}^{m \times n}$ is a full-ranked real-valued matrix with $m$ strictly smaller than $n$, i.e., $m < n.$

Through Monte-Carlo experiments, I noticed that

$$\lambda_{\max} (A) \geq \lambda_{\max}(BA B^\dagger),$$ where $\lambda_{\max}(\cdot)$ denotes the maximum eigenvalue of the argument. Moreover, matrix $B^\dagger$ stands for the pseudo-inverse of $B$, i.e., $B^\dagger =B^T(BB^T)^{-1}$.

I am wondering where this inequality comes from.

For more illustration, one can run the following short code in Matlab.

n=30; 
m=29;
c=0;

for i=1:1000;

  Q = randn(n,n);
  eigen_mean = 0.1; %can be made anything, 
   A = Q' * diag(abs(eigen_mean+randn(n,1))) * Q;  %A random symmetric positive definite   
   B=randn*randn(m,n);

      if max(eig(A))< max(eig(B * A * pinv(B)))
                 c = c +1 ;
      end
end

c

Everytime $c$ is returned zeor, since $\lambda_{\max} (A)$ is apparently never smaller than $ \lambda_{\max}(BA B^\dagger).$

$\endgroup$
4
  • $\begingroup$ What is $B^\dagger$? Also, is symmetric implied by positive definite? $\endgroup$ Jun 8, 2018 at 17:53
  • $\begingroup$ As mentioned above, $B^{\dagger}$ is the pseudo-inverse of matrix $B$. Besides being positive definite, matrix $A$ is also symmetric. I edited the question. Thank you. $\endgroup$
    – Amir Amini
    Jun 8, 2018 at 17:58
  • $\begingroup$ Notice that this formula for the pseudo-inverse applies only if $B$ is full rank. $\endgroup$ Jun 8, 2018 at 19:05
  • $\begingroup$ Thanks again. Matrix $B$ is guaranteed to be full-ranked in my application which I forgot to mention. Edited! $\endgroup$
    – Amir Amini
    Jun 8, 2018 at 19:12

1 Answer 1

3
$\begingroup$

Let $C=BAB^+=BAB^T(BB^T)^{-1}$. Note that $BAB^T$ and $(BB^T)^{-1}$ are $m\times m$ symmetric $>0$ matrices and, therefore, their product $C$ is diagonalizable and has only $>0$ eigenvalues.

More precisely, $C$ is similar to the following $>0$ symmetric mtrix

$S=(BB^T)^{-1/2}BAB^T(BB^T)^{-1/2}=[(BB^T)^{-1/2}B]A[(BB^T)^{-1/2}B]^T$.

For every vector $x\in\mathbb{R}^m$, $x^TSx=y^TAy$ where $y=[(BB^T)^{-1/2}B]^Tx$.

Then $x^TSx\leq \rho(A)||y||^2$ where $||y||^2=x^T(BB^T)^{-1/2}BB^T(BB^T)^{-1/2}x=||x||^2$ and we are done.

$\endgroup$
3
  • 2
    $\begingroup$ Just to make it more readable, $S=X^{-1}\left[BAB^T{\left(BB^T\right)}^{-1}\right]X$ with $X={\left(BB^T\right)}^{1/2}$. Great answer! +1 $\endgroup$ Jun 9, 2018 at 19:47
  • $\begingroup$ What a nice solution! Thanks a lot $\endgroup$
    – Amir Amini
    Jun 10, 2018 at 0:17
  • $\begingroup$ Thanks for the above compliments. $\endgroup$
    – user91684
    Jun 11, 2018 at 16:41

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.