I am interested in an effecient way of showing that the $n \times n$ matrix, \begin{pmatrix} 2&1&1& & 1\\ 1&3&1& \cdots & 1\\ 1&1&4& & 1\\ &\vdots& &\ddots& \vdots\\ 1&1&1& \cdots & n+1 \end{pmatrix} is positive definite.

This is an old qualifier question, so it should not require extensive brute force computation.

Sub-question: Do row operations affect positive-definiteness?

  • $\begingroup$ If the diagonal elements were $a_{ii} \geq n,$ one could write out $x^T Ax$ and see that it must be positive because $x^T Ax$ can be written as the sum of squares. Showing that the eigenvalues (pivots) are all positive seems to be out of the question. Finding $p(\lambda)$ and showing that there are $n$ sign changes in the polynomial seems out of the question as well. Someone clever might be able to find an $R$ such that $A = R^T R,$ but I am looking for a method that could be generalized to similar-type matrices. Thanks in advance. $\endgroup$ – Merkh Apr 20 '16 at 20:27

Observe that \begin{align} \begin{pmatrix} 2&1&1& \cdots & 1\\ 1&3&1& \cdots & 1\\ 1&1&4& \cdots & 1\\ \vdots&\vdots&\vdots &\ddots& \vdots\\ 1&1&1& \cdots & n+1 \end{pmatrix} = \begin{pmatrix} 1&1&1& \cdots & 1\\ 1&1&1& \cdots & 1\\ 1&1&1& \cdots & 1\\ \vdots&\vdots&\vdots &\ddots& \vdots\\ 1&1&1& \cdots & 1 \end{pmatrix} + \begin{pmatrix} 1&&& & \\ &2&& & \\ &&3& & \\ && &\ddots&\\ &&& & n \end{pmatrix} =A_1+A_2, \end{align} where $A_1$ and $A_2$ denote the corresponding decomposed matrices. Now, given ${\bf x}=(x_1,x_2,\ldots,x_n)^\top\in\mathbb{R}^n$, we have \begin{align} {\bf x}^\top A_1{\bf x}&= \begin{pmatrix} \displaystyle\sum_{k=1}^nx_k &\displaystyle\sum_{k=1}^nx_k &\cdots &\displaystyle\sum_{k=1}^nx_k \end{pmatrix} \begin{pmatrix} x_1\\x_2\\\vdots\\x_n \end{pmatrix} =\left(\sum_{k=1}^nx_k\right)^2\ge 0,\\ {\bf x}^\top A_2{\bf x}&= \begin{pmatrix} x_1&2x_2&\cdots&nx_n \end{pmatrix} \begin{pmatrix} x_1\\x_2\\\vdots\\x_n \end{pmatrix} =\sum_{k=1}^nk\cdot x_k^2. \end{align} If ${\bf x}\neq{\bf 0}$, at least one entry $x_k\ne 0$ for some $k$, and then the value ${\bf x}^\top A_2{\bf x}$ must be positive. Thus \begin{align} {\bf x}^\top\begin{pmatrix} 2&1&1& \cdots & 1\\ 1&3&1& \cdots & 1\\ 1&1&4& \cdots & 1\\ \vdots&\vdots&\vdots &\ddots& \vdots\\ 1&1&1& \cdots & n+1 \end{pmatrix}{\bf x} &={\bf x}^\top(A_1+A_2){\bf x}\\ &={\bf x}^\top A_1{\bf x}+{\bf x}^\top A_2{\bf x}\\ &\ge{\bf x}^\top A_2{\bf x}\\ &>0, \end{align} and we conclude that the matrix must be positive definite.

  • $\begingroup$ Decomposing the matrix into $A_1$ and $A_2$, very smart - thank you $\endgroup$ – Merkh Apr 20 '16 at 21:23
  • $\begingroup$ You are welcome! :) $\endgroup$ – Solumilkyu Apr 20 '16 at 21:31

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.