3
$\begingroup$

Let $A$ be a real $n\times n$ matrix, with ones in the diagonal, and all of the other elements equal to $r$ with $0<r<1$.

How can I prove that the eigenvalues of $A$ are $1+(n-1)r$ and $1-r$, with multiplicity $n-1$?

$\endgroup$

marked as duplicate by Marc van Leeuwen, Davide Giraudo, user147263, Najib Idrissi, drhab Oct 2 '14 at 16:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Any ideas of your own...? $\endgroup$ – Andrew D. Hwang Feb 24 '14 at 22:36
12
$\begingroup$

The matrix $A$ can be expressed as $$ A=ruu^T+(1-r)I $$ where $u=(1,1,\ldots,1)\in\mathbb R^{n\times 1}$, and $I$ the identity matrix in $\mathbb R^{n\times n}$.

So if $Av=\lambda v$, with $v\ne 0$, then $$ \lambda v=Av=r\langle u,v\rangle u+(1-r)v $$ where $\langle\cdot,\cdot\rangle$ is the standard inner product in $\mathbb R^n$. The above implies that $$ (\lambda-1+r)v=r\langle u,v\rangle u, $$ which in turn implies that,

either

  • $\langle u,v\rangle =0$, which happens for $n-1$ linearly independent vectors (as many the the dimension of the perpendicular hyperspace to $u$), and in this case $$ \lambda=1-r, $$ and hence the eigenvlaue $\lambda=1-r$ has multiplicity $n-1$,

or

  • $\langle u,v\rangle \ne 0$, which means that $v$ is a multiple of $u$, and the corresponding eigenvalue is obtained for $v=u$: $$ (\lambda-1+r)u=r\langle u,u\rangle u, $$ i.e., $$ \lambda=r\langle u,u\rangle +1-r=r(n-1)+1. $$
$\endgroup$
  • $\begingroup$ Really great proof! $\endgroup$ – Léo Feb 24 '14 at 22:41
  • 4
    $\begingroup$ You can simplify your argument a lot if you simply write $$A=r\,uu^T+(1-r)I=nr\,\frac{uu^T}n+(1-r)\frac{uu^T}n+(1-r)(I-\frac{uu^T}n)\\ = (nr+1-r)\,\frac{uu^T}n+(1-r)\,(I-\frac{uu^T}n).$$ Then you read directly that the eigenvalues are $1-r$ with multiplicity $n-1$ and $nr+1-r=1+n(r-1)$ with multiplicity $1$. $\endgroup$ – Martin Argerami Feb 24 '14 at 22:59
6
$\begingroup$

The determinant is invariant if you add to any row (column) a linear combination of other rows (columns). Then you can first subtract to every row the row right below it and you get \begin{vmatrix} 1 -\lambda& r & r & \cdots & r\\ r & 1 -\lambda & r & \cdots & r\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ r & r & r & \cdots & 1-\lambda \end{vmatrix} equal to \begin{vmatrix} 1-r-\lambda & r-1+\lambda & 0 & \cdots & 0\\ 0 & 1-r-\lambda & r-1+\lambda & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ r & r & r & \cdots & 1-\lambda \end{vmatrix} and now starting on the second column add to each column the one on it right like \begin{vmatrix} 1-r-\lambda & 0 & 0 & \cdots & 0\\ 0 & 1-r-\lambda & r-1+\lambda & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ r & 2r & r & \cdots & 1-\lambda \end{vmatrix} and when you do it for all of them you have \begin{vmatrix} 1-r -\lambda& 0 & 0 & \cdots & 0\\ 0 & 1-r -\lambda& 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ r & 2r & 3r & \cdots & 1 + (n-1)r-\lambda \end{vmatrix} finally using the cofactor formula for the determinant you get the polynomial $$ (1-r-\lambda)^{n-1}(1+(n-1)r-\lambda)=0 $$ which has the roots you wanted.

$\endgroup$
1
$\begingroup$

It's clear that $1 - r $is an eigenvalue whose corresponding eigenspace is $n - 1$ dimensional (it's the null space of a matrix consisting only of $1$s).

On the other hand by inspection the column vector consisting only of 1s is an eigenvector with eigenvalue $1 + (n-1) r $and the multiplicity must be $1$ since we already have $n - 1$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.