4
$\begingroup$

I am wondering whether there is any relation between principal eigenvalue of sub matrix and the original matrix.

In fact I am facing a problem which is to select $n$ rows and $n$ columns from the original non-negative matrix to construct a new matrix. The principal eigenvalue of the small matrix selected need to be close to certain constant.

I have totally no idea how to start...

I guess figuring out the relation maybe a good starting point of this problem.

UPDATE: I set up a conceptual optimization problem, hope this can help on the understanding of my problem.

$\min |\max (xAx')-\lambda^*|$

s.t. $\lVert x\rVert_2=1$

$x_i=[w_iv_i]$

$v_i>0$

$w_i=\{0,1\}$

$\sum_i w_i=n$

$A$ is the original matrix, $n$ is the number of rows/columns I used to construct the small matrix, $\lambda^*$ is the target constant of the principal eigenvalue of small matrix.

What I want to know is the $w$ vector

$\endgroup$
1
  • 4
    $\begingroup$ There is an interlacing theorem due to Cauchy. $\endgroup$
    – user32309
    May 27, 2012 at 11:42

2 Answers 2

4
$\begingroup$

Likely, the best you're going to get will come from the Cauchy Interlace Theorem that @user32309 referred to. You can see a proof of the result here in the paper "Cauchy's Interlace Theorem for Eigenvalues of Hermitian Matrices" by Suk-Geun Hwang and it states

Theorem 1 (Cauchy Interlace Theorem). Let $A$ be a Hermitian matrix of order $n$, and let $B$ be a principal submatrix of $A$ of order $n - 1$. If $\lambda_n\leq \lambda_{n-1}\leq \dots\leq \lambda_2\leq \lambda_1$, lists the eigenvalues of $A$ and $\mu_n\leq \mu_{n-1}\leq \dots\leq \mu_3\leq \mu_2$ the eigenvalues of $B$, then $\lambda_n\leq \mu_n\leq\lambda_{n-1}\leq\mu_{n-1}\leq \dots\leq \lambda_2\leq \mu_2\leq\lambda_1$.

$\endgroup$
3
$\begingroup$

I am wondering whether there is any relation between principal eigenvalue of sub matrix and the original matrix.

I put out a paper with Terry Tao and others here (see Terry's blog post here) which provides an answer to this question (we first found the result here in the context of particle physics).

The result is as follows: Let $A$ be an $n\times n$ Hermitian matrix with eigenvalues $\lambda_i(A)$. Let $M_j$ be the $n-1\times n-1$ submatrix that results from deleting the $j$th row and column which has $n-1$ eigenvalues $\lambda_i(M_j)$. Let the eigenvectors of $A$ be $v_i$ with elements $v_{i,j}$. Then,

$$|v_{i,j}|^2\prod_{k=1;k\neq i}^n(\lambda_i(A)-\lambda_k(A))=\prod_{k=1}^{n-1}(\lambda_i(A)-\lambda_k(M_j))$$

Terry provided a plethora of proofs for this which I won't repeat here.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .