3
$\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$
  • 3
    $\begingroup$ There is an interlacing theorem due to Cauchy. $\endgroup$ – user32309 May 27 '12 at 11:42
1
$\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$

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.