2
$\begingroup$

I have a symmetric $n \times n$ matrix as follows. I want to find the eigenvalues of this Hessian matrix to state that it is not Positive Semi-Definite (i.e. some eigenvalues are negative while the others are non-negative). If I couldn't find all the eigenvalues, it would be enough for my purpose to find just one negative eigenvalue:

NOTE: I could have found the eigenvalues in the $2\times2$ and $3\times3$ case. I am looking for the general $n\times n$ case. $a_1$ and $a_2$ should be equal in order to have positive eigenvalues in $2\times 2$ case. Similarly, $a_1, a_2$ and $a_3$ should be equal in order to have positive eigenvalues in $3\times 3$ case. $$A=\begin{pmatrix} 2a_1&a_1+a_2&\dots &a_1+a_{n-1}&a_1+a_n\\ a_1+a_2&2a_2&\dots &a_2+a_{n-1}&a_2+a_n\\ \vdots&\vdots&&\vdots&\vdots\\ a_1+a_{n-1}&a_2+a_{n-1}&\dots&2a_{n-1}&a_{n-1}+a_n\\ a_1+a_n&a_2+a_n&\dots&a_n+a_{n-1}&2a_n \end{pmatrix}$$

So $A_{ij} = a_i+a_j$.

$\endgroup$
  • $\begingroup$ What is the question? $\endgroup$ – copper.hat Aug 6 '14 at 19:33
  • $\begingroup$ @copper.hat He wants either all the eigenvalues for that matrix (seems unlikely) or, barring that, when are all the eigenvalues non-negative? For $2\times 2$ and $3\times 3$ he says all eigenvalues are non-negative if and only if the $a_i$ are all equal. Presumably the $a_i$ are all positive? $\endgroup$ – Thomas Andrews Aug 6 '14 at 19:34
  • $\begingroup$ What optimization problem did this Hessian come from - could you post a little more details about it? I know there are already answers, I'm just curious. $\endgroup$ – Nick Alger Aug 7 '14 at 8:41
2
$\begingroup$

The matrix $A$ can be decomposed as $A=au^T+ua^T$ where $a\in\mathbb{R}^n$ is the vector containing $a_1,\ldots,a_n$ and $u\in\mathbb{R}^n$ is the vector of all ones. If $v\in\mathbb{R}^n$ is a vector perpendicular to both $a$ and $u$, then $Av=0$. Hence we always have $n-2$ eigenvalues equal to zero. For the last two eigenvalues, we have to cases.

In the first case, $a$ and $u$ are linearly dependent, i.e., $a=\alpha u$ for some $\alpha\in\mathbb{R}$: in this case $A=2\alpha uu^T$ and the last two eigenvalues are $0$ and $2\alpha n$. The associated eigenvectors are $\frac{u}{||u||}$ (for the non-zero eigenvalue) and any set of $n-1$ vectors orthogonal to $u$. All the eigenvalues are non-negative and the matrix is PSD.

In the second case, $a$ and $u$ are linearly independent. For our analysis, we can limit our attention, without loss of generality, to vectors $v\in\mathbb{R}^n$ in the span of $\{a,u\}$ (if this is not true, the component of $v$ that is orthogonal to both $a$ and $u$ cancels out, as discussed above). This means that there exist $\alpha,\beta\in\mathbb{R}$ such that $v=\alpha a+\beta u$. The eigenvalue equation $Av=\lambda v$ reduces to, on the LHS,

$$ Av=(au^T+ua^T)(\alpha a+\beta u)=\left((u^Ta) \alpha+(u^Tu)\beta\right)a +\left((a^Ta)\alpha+(a^Tu)\beta\right) u, $$

and on the RHS

$$ \lambda v= \lambda\alpha a +\lambda\beta u. $$

Since $a$ and $u$ are linearly independent, the equation has a solution iff the coefficients of $a$ and $u$ on the two sides match.

We therefore get a reduced $2 \times 2$ system of equations of the form

$$ \begin{bmatrix} u^Ta & ||u||^2\\||a||^2 & u^Ta \end{bmatrix}\begin{bmatrix}\alpha\\\beta\end{bmatrix}=\lambda \begin{bmatrix}\alpha\\\beta\end{bmatrix}. $$

Note that $||u||^2=n$. Intuitively, this makes sense, because we reduced our $n\times n$ eigenvalue problem to the $2 \times 2$ eigenvalue problem obtained by restricting the vectors to the 2-dimensional space spanned by $a$ and $u$.

A symbolic computation software informs me that the eigenvalues for the reduced $2 \times 2$ case are

$\lambda_{1,2}=u^Ta\pm\sqrt{n||a||^2}.$

(Note that this formula gives the right result also for the case $a=\alpha u$, although, technically, its derivation would not be correct.)

To conclude, the matrix A can be PSD or indefinite depending on $a$. E.g., if $a=u$, then it is PSD, but if $a$ is orthogonal to $u$, then it is indefinite.

$\endgroup$
3
$\begingroup$

Note that $A$ can be represented as $$A=a^T\otimes e+e^T\otimes a,$$ where $a=(a_1,\ldots,a_n)$ and $e=(1,\ldots,1)$. Hence $A$ has rank $\leq 2$ and can have at most two non-zero eigenvalues.

The corresponding column eigenvectors are linear combinations of $a^T$ and $e^T$. Writing $w=\alpha a+\beta e$, we get $$Aw^T=\bigl(\alpha (e,a)+\beta(e,e)\bigr) a^T+\bigl(\alpha (a,a)+\beta(a,e)\bigr) e^T,$$ where $(x,y)=x\cdot y^T=\sum_{k=1}^n x_k y_k$ denotes the usual scalar product. Therefore, the equation for the two nontrivial eigenvalues becomes $$\operatorname{det}\left(\begin{array}{cc} (e,a)-\lambda & (e,e) \\ (a,a) & (a,e)-\lambda \end{array}\right)=0,$$ or, equivalently, $$\lambda^2-2(e,a)\lambda+(e,a)^2-(e,e)(a,a)=0.$$ Yet in another form: $$\lambda^2-2n\langle a\rangle\lambda+n^2\left(\langle a\rangle^2-\langle a^2\rangle\right)=0\quad \Longrightarrow \quad \lambda_{\pm}=n\left[\langle a\rangle\pm\sqrt{\langle a^2\rangle}\right],$$ where $\langle x\rangle\displaystyle=\frac{\sum_{k=1}^n x_k}{n}$. Therefore $A$ is positive semi-definite iff $a_1=a_2=\ldots=a_n\geq 0$.

$\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.