# Positive Definite Proof Method

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?

• 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. – 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.
• Decomposing the matrix into $A_1$ and $A_2$, very smart - thank you – Merkh Apr 20 '16 at 21:23