11
$\begingroup$

Let $A,B\in M_n(\mathbb R)$, and $\ell$ a list of $n$ numbers sorted in some order (say, decreasing).

Let $\lambda_i(A)$ be the $i$th eigenvalue of $A$ with respect to the chosen order.

Finally, let $d(A,\ell) = ||\lambda(A)-\ell||_1 = \sum_{i = 1}^n |\lambda_i(A)-\ell_i|$ be the taxicab metric.

My question is as follows:

Given, $A,B,\ell$, is it possible to determine which of $d(A,\ell)$ or $d(B,\ell)$ is smaller without computing the eigenvalues of $A$ and $B$?

Note: The $d(A,\ell)$ can also be any other meaningful metric that determines the matrix which its eigenvalues are closer to the list $\ell$

Update: My solution (Not working!)

Let $\lambda$ and $\beta$ be the eigenvalues of $A$ and $B$ respectively. Clearly $det(A-\lambda I) = 0$ and $det(B-\beta I) = 0$ and $P_n(\lambda), P_n(\beta)$ are characteristic polynomial of $A,B$.

Let sort the eigenvalues $\beta = \{\beta_1,\beta_2,...\beta_n \}$ and $\lambda = \{\lambda_1,\lambda_2,...\lambda_n \}$ in chosen order (say, decreasing).

Let $\forall \ell_i \in \ell, i\in\{1,2,...,n\},$

if $\sum_{i=1}^{n} (det(A-\ell_i I)-det(B-\ell_i I)) > 0$ then eigenvalues of $B$ are closer to $\ell$ and if $\sum_{i=1}^{n} (det(A-\ell_i I)-det(B-\ell_i I)) < 0$ then eigenvalues of $A$ are closer to $\ell$. Notice, since we don't actually need to calculate the eigenvalues of $A, B$, we don't need to solve the characteristic polynomial of $A, B$, It is enough to form the $det(A-\ell_i I)-det(B-\ell_i I)$, where $\ell_i$ is known then continue as described.

Is this solution right? and is it easier to find determinant of $n$ matrices than finding the eigenvalues of a $n \times n$ matrix?

|cite|improve this question
$\endgroup$
  • $\begingroup$ @AlexSilva thanks $\endgroup$ – No one Dec 21 '16 at 9:17
  • 1
    $\begingroup$ Yeah! I made a mistake. I will think in another solution. $\endgroup$ – Alex Silva Dec 21 '16 at 9:30
  • $\begingroup$ @AlexSilva I updated my question and provided a solution. Please take a look at it. $\endgroup$ – No one Dec 21 '16 at 21:17
  • 2
    $\begingroup$ Costs of determinant calculation Costs of eigenvalue calculation and at wikipedia The cost of eigenvalue calculation is about twice the costs of LU needed for determinant calculation. If you need $n>2$ determinants you are better off with eigenvalue calculation. $\endgroup$ – Tobias Dec 21 '16 at 21:47
  • 1
    $\begingroup$ By the way your assumption is wrong: $l_i=0$, $A=\mathbf{1}\in\mathbb{R}^n$, $B=\begin{pmatrix}n&\mathbf{0}\\\mathbf{0}&\mathbf{0}\end{pmatrix}\in\mathbb{R}^n$. $d(A,l)=n$, $d(B,l)=n$, $\operatorname{det}(A-l_i\mathbf{1})=1$, $\operatorname{det}(B-l_i\mathbf{1})=0$. $\endgroup$ – Tobias Dec 21 '16 at 21:58

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.