2
$\begingroup$

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

Let $A$ be an $n\times 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?

$\endgroup$
  • $\begingroup$ Did you try a few simple values for $a$ like $a = -1, 0, 1$? $\endgroup$ – John Hughes Mar 9 '15 at 19:02
  • $\begingroup$ There are several ways to tackle this problem and they all depend on how much linear algebra you've studied. Is this your first linear algebra course or are you a veteran? $\endgroup$ – mathreadler Mar 9 '15 at 19:09
1
$\begingroup$

Your matrix can be written as $$ \mathbf{M}(a) = (1-a)\mathbf{I} + a\mathbf{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} + a\mathbf{1}\mathbf{1}^\top)\\ &=& \mathrm{det}((1-a)\mathbf{I})\left(1+a\mathbf{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 $a\leq -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.

$\endgroup$
  • $\begingroup$ I notice that there are 3 answers that give conflicting answers. So perhaps I have a mistake. However, I think this is a valid solution approach that should give you a comprehensive answer. $\endgroup$ – Peder Mar 9 '15 at 19:57
  • 1
    $\begingroup$ You could be correct, the Gershgorin approach below only gives a pessimistic estimate. It ensures all eigenvalues are inside the discs, so the eigenvalues could still be in the right half plane even if the circles overlap the left half plane a bit. $\endgroup$ – mathreadler Mar 9 '15 at 20:32
  • 1
    $\begingroup$ To see that $a>1$ is never SPD for $n>1$, note that the determinant is negative for $n=2$, then for $n>2$ use Sylvester's criterion and look at the top-left $2\times 2$ minor. $\endgroup$ – user7530 Mar 9 '15 at 21:00
2
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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