1
$\begingroup$

Let $A \in \mathbb{R}^{n \times n}$ be a symmetric positive semi-definite matrix with sum of each row equals to zero.

Is my intuition true that the following inequality always hold?

$$\lambda_{\max} (B^T B) \leq \lambda^2_\max (A),$$

where $B \in \mathbb{R}^{(n-1) \times n}$ is obtained by removing one arbitrary row of $A$, i.e., matrix $B$ has exactly the same entries as $A$ except for one row which is omitted. Also, notation $\lambda_\max$ stands for the maximum eigenvalue.

Can we possibly extend the aforementioned inequality for $m$ number of rows omitted? ($m<n$)

For better illustration, one may run the following piece of code in Matlab:

    n=12;
flag=0;
format long 

for i=1:1000  % running for 1000 random A

 %%%%%%%%%%creating rondom A:
w=1.0; 
adj=zeros(n,n);
k=1;
for j=1:n-1 % Go through each row
    for k=j+1:n % Go through each column of the row chosen above
    adj(j,k)=round(rand*w);
    if adj(j,k)>1
       adj(j,k)=1;
    end
    end
end

adj=adj+adj';

 Laplacian=adj-diag(sum(abs(adj)));
 A=-Laplacian; 
   %%%%%%%%%%% A is now created


 max_eig_A_square= max(eig(A))^2;

 B=A(1:end-1,1:end);

  max_eig_BTB = max(eig(B'*B));

    %%%%%% Look whether our hypothesis is contradicted or not
 if max_eig_BTB > max_eig_A_square
    flag=1; 
    A
    max_eig_BTB
    max_eig_A_square
 end

end

flag

Running for 1000 random $A$, 'flag' is returned zero as was initially set to zero. Sometimes flag is returned 1, but when we compare the values of 'max_eig_BTB' and 'max_eig_A_square', they are quite equal until say the 16th digit after the floating point. (which might be due to some numerical limitations).

$\endgroup$
  • $\begingroup$ The use of the term "row reduced" is confusing. Row reduction typically refers to the application of Gaussian Elimination, not literally omitting a row to form a rectangular matrix. $\endgroup$ – Theo Bendit Sep 6 '18 at 2:06
  • $\begingroup$ Thank you for the point. Edited! $\endgroup$ – Amir Amini Sep 6 '18 at 2:59
  • $\begingroup$ If we remove no rows, then we find that $$ \lambda_{\max}^2(A) \leq \lambda_{\max}(A^TA) $$ removing any number of rows from $A$ will not be enough to reverse this inequality in general $\endgroup$ – Omnomnomnom Sep 6 '18 at 3:13
  • $\begingroup$ It is true, however, that $$ \lambda_{\max}(B^TB) \leq \lambda_{\max}(A^TA) $$ perhaps this is an interesting result for your purposes $\endgroup$ – Omnomnomnom Sep 6 '18 at 3:16
  • $\begingroup$ Thank you, I think $\lambda^2_\max(A) = \lambda_\max(A^T A)$ for this special form of $A$, i.e., symmetric positive semi-definite with zero row sum. Any ideas on that? $\endgroup$ – Amir Amini Sep 6 '18 at 4:53

Your Answer

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

Browse other questions tagged or ask your own question.