Xrfgtjtk

I came across this linear algebra question but I have no clue on how to tackle it. Can someone help?

Let $A$ be an $ntimes n$ matrix, with all off-diagonal entries equal to $a$, and all diagonal entries equal to $1$. For which value of $a$, is this matrix definitely positive definite? For which values of $a$, does there exist a matrix that is positive definite?

Another approach is to identify the matrix as a circulant matrix and use the result that circulant matrices always have an eigendecomposition with eigenvectors which are the complex exponentials and eigenvalues are the Fourier coefficients (this corresponds to signal processing that linear filtering is multiplication in "Fourier domain"). So you can just Fourier-transform [1,a,a,a...,a] and see what expressions you get for the coefficients. If they are all real it corresponds to a so called "zero-phase" filter. (May be a bit confusing if you are not an EE, but it's really exciting otherwise)

To compute the determinant of $A-xI_n$ add all the columns to the first one and then subtract the first row from the others and then expand along the first column to get

$$det(A)=(1+(n-1)a-x)((n-2)a+1-x)^{n-1}$$
so we get the spectrum of $A$:

$$operatorname{sp}(A)={1+(n-1)a,1+(n-2)a}$$
hence the matrix $A$ is definite positive iff their eigenvalues are positive iff $a>-frac1{n-2}$ for $n>2$ and $a>-1$ for $n=2$.

Your matrix can be written as
$$
mathbf{M}(a) = (1-a)mathbf{I} + amathbf{1}mathbf{1}^top.
$$
Specifically we have $mathbf{M}(0)=mathbf{I}$, which is positive definite (all eigenvalues are zero). Since $mathbf{M}(a)$ defines a continuous path of matrices it will remain positive definite as long as it doesn't cross the boundary of the positive definite cone. This happens when one of the eigenvalues become zero, which in turn implies that the determinant is zero (i.e. $mathrm{det}(mathbf{M}(a))=0$).
By the matrix determinant lemma we have
begin{eqnarray}
mathrm{det}(mathbf{M}(a)) &=& mathrm{det}((1-a)mathbf{I} + amathbf{1}mathbf{1}^top)\
&=& mathrm{det}((1-a)mathbf{I})left(1+amathbf{1}^top((1-a)mathbf{I})^{-1}mathbf{1}right)\
&=& (1-a)^n(1+na/(1-a))\
&=& (a-a)^{n-1}(1+(n-1)a)
end{eqnarray}
Note that $1+(n-1)a=0$ when $a=-1/(n-1)$ and $(1-a)=0$ when $a=1$. Therefore the matrix is positive definite for all $-1/(n-1)<a<1$. There are no other zero-crossings so, for $aleq -1/(n-1)$ it will not be positive definite. For $a=1$ the zero has order $n-1$ so you need to investigate closer to find out it it is positive definite for any value $a>1$. My guess is that it won't be positive definite. Also, note that in the special case $n=1$ the matrix $M(a)=1$ is independent of $a$ and positive definite.

One approach is by the Geshgorin/Hirschhorn circle theorem: http://en.wikipedia.org/wiki/Gershgorin_circle_theorem . Then we see that R = |a|(n-1) and midpoint of all circles is 1. So by the theorem, if |a|(n-1) < 1 we are sure that all eigenvalues are in the right half plane and since the matrix is symmetric, they must all be real.