25
$\begingroup$

I have the following $n\times n$ matrix:

$$A=\begin{bmatrix} a & b & \ldots & b\\ b & a & \ldots & b\\ \vdots & \vdots & \ddots & \vdots\\ b & b & \ldots & a\end{bmatrix}$$

where $0 < b < a$.

I am interested in the expression for the determinant $\det[A]$ in terms of $a$, $b$ and $n$. This seems like a trivial problem, as the matrix $A$ has such a nice structure, but my linear algebra skills are pretty rusty and I can't figure it out. Any help would be appreciated.

$\endgroup$
  • 3
    $\begingroup$ Please do not use math displays in titles. $\endgroup$ – Mariano Suárez-Álvarez Nov 29 '11 at 6:23
  • 2
    $\begingroup$ This isn't a duplicate of math.stackexchange.com/questions/84206/… but the answer to this question appears in the answers to that question. $\endgroup$ – Gerry Myerson Nov 29 '11 at 6:23
  • $\begingroup$ There's a geometric, rather than algebraic, way of viewing it that makes it easy to understand. I've posted it below. $\endgroup$ – Michael Hardy Nov 29 '11 at 15:56
  • $\begingroup$ I've been away for a while -- I apologize for the late acceptance of an answer (I've looked at this before I left, but haven't had time to pick the best answer.) Also, @MarianoSuárez-Alvarez, I apologize for putting the matrix into the title... Thanks for correcting me on that. $\endgroup$ – M.B.M. Dec 13 '11 at 6:40
30
$\begingroup$

Add row 2 to row 1, add row 3 to row 1,..., add row $n$ to row 1, we get $$\det(A)=\begin{vmatrix} a+(n-1)b & a+(n-1)b & a+(n-1)b & \cdots & a+(n-1)b \\ b & a & b &\cdots & b \\ b & b & a &\cdots & b \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ b & b & b & \ldots & a \\ \end{vmatrix}$$ $$=(a+(n-1)b)\begin{vmatrix} 1 & 1 & 1 & \cdots & 1 \\ b & a & b &\cdots & b \\ b & b & a &\cdots & b \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ b & b & b & \ldots & a \\ \end{vmatrix}.$$ Now add $(-b)$ of row 1 to row 2, add $(-b)$ of row 1 to row 3,..., add $(-b)$ of row 1 to row $n$, we get $$\det(A)=(a+(n-1)b)\begin{vmatrix} 1 & 1 & 1 & \cdots & 1 \\ 0 & a-b & 0 &\cdots & 0 \\ 0 & 0 & a-b &\cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & a-b \\ \end{vmatrix}=(a+(n-1)b)(a-b)^{n-1}.$$

$\endgroup$
  • 3
    $\begingroup$ I like this solution due to its simplicity and elegance. Other solutions are great too. $\endgroup$ – M.B.M. Dec 13 '11 at 6:42
  • $\begingroup$ nice solution. easy to understand. $\endgroup$ – prasad Apr 22 '13 at 6:33
  • $\begingroup$ add (−b) of row 1 to row 2 - there is no $-b$ in row $1$, what you have done here? $\endgroup$ – tarit goswami Oct 7 '18 at 4:48
16
$\begingroup$

SFAICT this route hasn't been mentioned yet, so:

Consider the decomposition

$$\small\begin{pmatrix}a&b&\cdots&b\\b&a&\cdots&b\\\vdots&&\ddots&\vdots\\b&\cdots&b&a\end{pmatrix}=\begin{pmatrix}a-b&&&\\&a-b&&\\&&\ddots&\\&&&a-b\end{pmatrix}+\begin{pmatrix}\sqrt b\\\sqrt b\\\vdots\\\sqrt b\end{pmatrix}\cdot\begin{pmatrix}\sqrt b&\sqrt b&\cdots&\sqrt b\end{pmatrix}$$

Having this decomposition allows us to use the Sherman-Morrison-Woodbury formula for determinants:

$$\det(\mathbf A+\mathbf u\mathbf v^\top)=(1+\mathbf v^\top\mathbf A^{-1}\mathbf u)\det\mathbf A$$

where $\mathbf u$ and $\mathbf v$ are column vectors. The corresponding components are simple, and thus the formula is easily applied (letting $\mathbf e$ denote the column vector whose components are all $1$'s):

$$\begin{align*} \begin{vmatrix}a&b&\cdots&b\\b&a&\cdots&b\\\vdots&&\ddots&\vdots\\b&\cdots&b&a\end{vmatrix}&=\left(1+(\sqrt{b}\mathbf e)^\top\left(\frac{\sqrt{b}}{a-b}\mathbf e\right)\right)(a-b)^n\\ &=\left(1+\frac{nb}{a-b}\right)(a-b)^n=(a+(n-1)b)(a-b)^{n-1} \end{align*}$$

where we used the fact that $\mathbf e^\top\mathbf e=n$.

$\endgroup$
  • 3
    $\begingroup$ This is very pretty! $\endgroup$ – M.B.M. Jul 28 '12 at 5:35
  • 1
    $\begingroup$ Can't you put $\mathbf u:=\mathbf e$ and $\mathbf v:=b\mathbf e$ (or vice versa) to avoid the radicals? $\endgroup$ – yo' Oct 2 '15 at 20:09
  • $\begingroup$ @yo, yes, that can be done. $\endgroup$ – J. M. is a poor mathematician Oct 6 '15 at 12:49
5
$\begingroup$

Subtract the bottom row from each of the other rows, then expand along some convenient row or column.

$\endgroup$
5
$\begingroup$

This is indeed an easy problem. Let $J$ be the square matrix with every entry equal to $1$. Your problem is equivalent to finding the determinant of $\lambda I + \mu J$ for arbitrary $\lambda, \mu$. Let $v=\left(\frac1{\sqrt{n}}, \frac1{\sqrt{n}},\ldots,\frac1{\sqrt{n}}\right)^\top$ and $e=(1,0,\ldots,0)^\top$. Then $J=nvv^\top$. Take any orthogonal matrix with its first column equal to $v$. Then $V^\top(\lambda I + \mu J)V = \lambda I+\mu nee^\top = \textrm{diag}\left(\lambda+\mu n,\lambda,\ldots,\lambda\right)$. Hence $\det(\lambda I + \mu J) = (\lambda+\mu n)\lambda^{n-1}$. Put $\lambda=a-b$ and $\mu=b$, we get the answer to your question as $[a+(n-1)b](a-b)^{n-1}$.

$\endgroup$
4
$\begingroup$

The matrix can be diagonalized. All it takes is a bit of geometry. We have

$$A=\begin{bmatrix}a&b&\cdots&b\\b&a&\cdots&b\\\vdots& &\ddots&\vdots\\b&\cdots&b&a\end{bmatrix}.$$

This is a linear combination of the matrices $P$ and $Q=I-P$ where $P$ is the matrix of the orthogonal projection onto the $1$-dimensional space of column vectors in which all scalar components are equal, i.e. the space $$ \left\{\begin{bmatrix} x \\ x \\ x \\ \vdots \\ x \end{bmatrix} : x \text{ is a scalar} \right\}. $$ We have $$ P = \begin{bmatrix} 1/n & 1/n & \ldots & 1/n \\ 1/n & 1/n & \ldots & 1/n \\ \vdots & \vdots & & \vdots \\ 1/n & 1/n & \ldots & 1/n \end{bmatrix} $$ (all entries are $1/n$), so that $$ P \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} \bar{x} \\ \bar{x} \\ \bar{x} \\ \vdots \\ \bar{x} \end{bmatrix} $$ where $\bar{x} = (x_1+\cdots+x_n)/n$ is the average of the components, and $$ Q \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} x_1-\bar{x} \\ x_2-\bar{x} \\ x_3-\bar{x} \\ \vdots \\ x_n-\bar{x} \end{bmatrix}. $$ We want $$ A = \alpha P + \beta Q. $$ Looking at the diagonal elements we have $$ \alpha\cdot\frac 1n + \beta \left(1-\frac 1n\right) = a, $$ and from the off-diagonal elements we get $$ \alpha\cdot\frac 1n - \beta \cdot\frac 1n =b. $$ Hence $$ \alpha = a + (n-1)b \qquad\text{and}\qquad\beta= a-b. $$

Since $P$ projects orthogonally onto a $1$-dimensional subspace and $Q$ is the complementary orthogonal projection onto an $(n-1)$-dimensional subspace, the matrix $\alpha P+\beta Q$ can be diagonalized as $$ \begin{pmatrix} \alpha \\ & \beta \\ & & \beta \\ & & & \beta \\ & & & & \ddots \\ & & & & & \beta \end{pmatrix}. $$ The determinant is therefore $$ \alpha\beta^{n-1}. $$

$\endgroup$
3
$\begingroup$

Hint: We can assume that the ground ring is a field, and that $b\neq0$. Consider the subspace formed by the vectors with equal coordinates, and the subspace formed by the vectors whose coordinates add up to $0$; note that these two subspaces are eigenspaces; compute the corresponding eigenvalues; and conclude.

EDIT. To find the eigenspaces of $A$ you can add $b-a$ to it, to make all the entries equal to $b$. (Adding a scalar to $A$ doesn't affect the eigenspaces.)

$\endgroup$
3
$\begingroup$

Define $\mathbf{1} = \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}$. Take $P = b\mathbf{1} \mathbf{1}^T$ (outer product!) and observe that \[ A=P + (a-b) I .\]

We begin with observations on the matrix $P = b\mathbf{1} \mathbf{1}^T$:

  1. All rows and columns are equal and $b>0$, so P is a rank $1$ matrix. Thus $\lambda_1=0$ is an eigenvalue of multiplicity $n-1$.
  2. $P \mathbf{1} = b\mathbf{1} \mathbf{1}^T\mathbf{1} = n b \mathbf{1}$. Thus $\lambda_2 = nb$ is an eigenvalue of multiplicity $1$.

We now use the following theorem:

Theorem: If $r$ is an eigenvalue of $T$, then $r+s$ is an eigenvalue of $T+sI$.

Proof: Since $r$ is an eigenvalue of $T$, there exists $\mathbf{v}$ such that $ T \mathbf{v} = r \mathbf{v}$. Then \[ (T + sI)\mathbf{v} = T \mathbf{v} + sI \mathbf{v} = r \mathbf{v} + s \mathbf{v} = (r + s) \mathbf{v}. \quad \text{qed}\]

Thus the eigenvalues of $P+(a-b)I$ will be $\lambda_1 = (0+(a-b))$ with multiplicity $n-1$ and $\lambda_2 = nb + (a-b)$ with multiplicity one. Since the determinant is the product of the eigenvalues, we have that \[ \det(A) =\begin{vmatrix} a & b & \ldots & b\\ b & a & \ldots & b\\ \vdots & \vdots & \ddots & \vdots\\ b & b & \ldots & a\end{vmatrix} = \det(P+(a-b)I) = (a-b)^{n-1} (nb+a-b) . \]

$\endgroup$
  • $\begingroup$ I love this prove, the theorem stated is the central core in inverse power method for approximating eigenvectors of a matrix with an approximation to his eigenvalue. $\endgroup$ – Ernesto Iglesias Oct 8 '18 at 5:42
2
$\begingroup$

Consider the $n\times n$ matrix $B$ with entries $-b$ everywhere, except on the main diagonal where it has entries $0$. Now $\det A=\det(aI-B)$ is just the value of the characteristic polynomial $\chi_B\in K[X]$ at $X=a$. For $X=b$ the matrix $bI-B$ clearly has rank at most$~1$ (all columns are equal), so by rank-nullity the eigenspace of $B$ for the eigenvalue $b$ has dimension at least $n-1$, and $\chi_B$ is divisible by $(X-b)^{n-1}$. The final eigenvalue must make their sum $\operatorname{tr}(B)=0$ so it is $-(n-1)b$, and the final factor of $\chi_B$ is $X+(n-1)b$. So$$ \det A=\chi_B[X:=a] = (a-b)^{n-1}(a+(n-1)b). $$

$\endgroup$
1
$\begingroup$

Just to give my two cents: if $a=b$ the result is trivially zero; else, we can write $A = (a-b){\rm Id}_n + b{\bf 1}_n$, where ${\bf 1}_n$ is a matrix consisting only of $1$'s. Then $$\begin{align}\det(A) &= \det((a-b){\rm Id}_n+b{\bf 1}_n) = (a-b)^n \det\left({\rm Id}_n + \frac{b}{a-b}{\bf 1}_n\right) \\ &\stackrel{(\ast)}{=} (a-b)^n\left(1 + {\rm tr}\left(\frac{b}{a-b} {\bf 1}_n\right) \right) = (a-b)^n\left(1+ \frac{nb}{a-b}\right) \\ &= (a-b)^n + nb(a-b)^{n-1} = (a-b)^{n-1}(a+(n-1)b),\end{align}$$where in $(\ast)$ we used the "Sylvester-like" formula $\det({\rm Id}_n+B) = 1+{\rm tr}(B)$, valid for matrices $B$ with ${\rm rank}(B)=1$.

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