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

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

• 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. – Theo Bendit Sep 6 '18 at 2:06
• Thank you for the point. Edited! – Amir Amini Sep 6 '18 at 2:59
• 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 – Omnomnomnom Sep 6 '18 at 3:13
• It is true, however, that $$\lambda_{\max}(B^TB) \leq \lambda_{\max}(A^TA)$$ perhaps this is an interesting result for your purposes – Omnomnomnom Sep 6 '18 at 3:16
• 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? – Amir Amini Sep 6 '18 at 4:53