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$
  • $\begingroup$ What is $B^\dagger$? Also, is symmetric implied by positive definite? $\endgroup$ – Fimpellizieri Jun 8 '18 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 '18 at 17:58
  • $\begingroup$ Notice that this formula for the pseudo-inverse applies only if $B$ is full rank. $\endgroup$ – Fimpellizieri Jun 8 '18 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 '18 at 19:12
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$
  • 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$ – Fimpellizieri Jun 9 '18 at 19:47
  • $\begingroup$ What a nice solution! Thanks a lot $\endgroup$ – Amir Amini Jun 10 '18 at 0:17
  • $\begingroup$ Thanks for the above compliments. $\endgroup$ – loup blanc Jun 11 '18 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.