Relationship between the maximum eigenvalues of a matrix and its row-manipulated form

181 Views Asked by At

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