18
$\begingroup$

Hi guys I am working with this and I am trying to prove to myself that n by n matrices of the type zero on the diagonal and 1 everywhere else are invertible.

I ran some cases and looked at the determinant and came to the conclusion that we can easily find the determinant by using the following $\det(A)=(-1)^{n+1}(n-1)$. To prove this I do induction

n=2 we have the $A=\begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix}$ $\det(A)=-1$ and my formula gives me the same thing (-1)(2-1)=-1

Now assume if for $n \times n$ and $\det(A)=(-1)^{n+1}(n-1)$

Now to show for a matrix B of size $n+1 \times n+1$. I am not sure I was thinking to take the determinant of the $n \times n$ minors but I am maybe someone can help me. Also is there an easier way to see this is invertible other than the determinant? I am curious.

$\endgroup$
18
$\begingroup$

This is easy to calculate by row reduction:

Add all rows to first: $$\det(A) =\det \begin{bmatrix} 0 & 1 & 1 &...&1 \\ 1 & 0 & 1 &...&1 \\ 1 & 1 & 0 &...&1 \\ ... & ... & ... &...&... \\ 1 & 1 & 1 &...&0 \\ \end{bmatrix}=\det \begin{bmatrix} n-1 & n-1 & n-1 &...&n-1 \\ 1 & 0 & 1 &...&1 \\ 1 & 1 & 0 &...&1 \\ ... & ... & ... &...&... \\ 1 & 1 & 1 &...&0 \\ \end{bmatrix} \\ =(n-1)\det \begin{bmatrix} 1 & 1 & 1 &...&1 \\ 1 & 0 & 1 &...&1 \\ 1 & 1 & 0 &...&1 \\ ... & ... & ... &...&... \\ 1 & 1 & 1 &...&0 \\ \end{bmatrix}=(n-1)\det \begin{bmatrix} 1 & 1 & 1 &...&1 \\ 0 & -1 & 0 &...&0 \\ 0 & 0 & -1 &...&0 \\ ... & ... & ... &...&... \\ 0 & 0 & 0 &...&-1 \\ \end{bmatrix}$$

where in the last row operation I subtracted the first row from each other row.

This shows $$\det(A)=(n-1)(-1)^{n-1}$$

$\endgroup$
34
$\begingroup$

If you have studied eigenvalues and eigenvectors there is a very easy proof.

Let $A$ be your $n\times n$ matrix, with $n\ge2$. Then $A+I$ is the matrix consisting entirely of $1$s, which clearly has $n-1$ zero rows after row-reduction. Therefore $A$ has eigenvalue $-1$, repeated (at least) $n-1$ times, and since ${\rm trace}(A)=0$, the other eigenvalue is $n-1$.

Since every eigenvalue of $A$ is non-zero, the determinant of $A$ is non-zero, so $A$ is invertible.

$\endgroup$
  • 9
    $\begingroup$ Clearly, this also proves the said formula $\det A = (-1)^{n-1}(n-1)$. $\endgroup$ – Jeppe Stig Nielsen Jun 5 '15 at 14:37
  • $\begingroup$ @JeppeStigNielsen How do we conclude that the multiplicity of the eigenvalue $-1$ is $n-1$? $\endgroup$ – Akash Gaur Aug 3 at 15:34
  • $\begingroup$ @AkashGaur The argument of the answer claimed to prove that the $n$ eigenvalues of $A$ are $-1,-1,\ldots,-1$ ($n-1$ times), and $n-1$ (once). That was not my statement. I just commented that if those $n$ numbers are really the eigenvalues, then their product is the determinant. $\endgroup$ – Jeppe Stig Nielsen Aug 4 at 17:39
17
$\begingroup$

Here's an alternative approach. The Woodbury matrix identity says that if we start with an invertible matrix $B$ and update it by adding a product of matrices $UCV$, then the inverse of the sum is, $$(B + U C V)^{-1} = B^{-1} - B^{-1} U (C^{-1} + V B^{-1} U)^{-1} V B^{-1}.$$ This holds whenever

  1. all the matrices in the formula have sizes such that the formula makes sense, and
  2. all the inverses on the right hand side in the formula exist.

The Woodbury formula can be proved by direct verification (multiply it out), and can be derived in a number of straightforward ways - see the wikipedia article linked above for more details.

Now in your situation we can take:

  • $B := -I$
  • $C := 1$
  • $U = \mathbf{1}$, the column vector of all ones
  • $V = \mathbf{1}^T$, the row vector of all ones,

so that $B + U C V = -I + \mathbf{1}\mathbf{1}^T = A$ is the matrix of all ones except on the diagonal that we wish to invert. In this case the Woodbury formula becomes,

\begin{align} (-I + \mathbf{1}\mathbf{1}^T)^{-1} &= -I - \mathbf{1}(1 - \mathbf{1}^T I \mathbf{1})^{-1}\mathbf{1}^T \\ &= -I - \mathbf{1}(1 - n)^{-1}\mathbf{1}^T \\ &= -I + \frac{1}{n-1}\mathbf{1}\mathbf{1}^T. \end{align}

So, here we have proved that the matrix is invertible for all $n$-by-$n$ matrices whenever $n > 1$ (Ie., it is not a scalar). Further we have a complete formula for the inverse, $$\boxed{A^{-1} = -I + \frac{1}{n-1}\mathbf{1}\mathbf{1}^T}$$

$\endgroup$
9
$\begingroup$

Using the Gauss-Jordan method it is possible to think of elementary row operation which would convert such a $n\times n$ matrix to the identity matrix. Thus an inverse exist.

Namely if you multiply the first row by $n-2$, subtract the remaining $n-1$ rows from it once, then you get $1-n$ for the first element followed by only zeros for the other elements of the first row. By normalizing this row you get a one followed by zeros, which can then be used to clear the first column of the other rows. This process can be repeated for the remaining rows until the final two rows, which can be swapped to obtain the identity matrix.

If you wish to actually calculate the inverse you could make use of symmetry, namely all diagonals will be equal and all other elements will be equal. This information can already be obtained after reducing the first row, namely all diagonals will be equal to $\frac{2-n}{n-1}$ and all other elements will be equal to $\frac{1}{n-1}$.

$\endgroup$
  • $\begingroup$ Clever I like it I think all answers are good but this is clever. $\endgroup$ – Kori Jun 5 '15 at 4:24
4
$\begingroup$

A square matrix is invertible if its columns (or equivalently, rows) are linearly independent. Let $v_i$ be the $i$th column of the matrix. If $$ c_1v_1 + c_2v_2 + \dots + c_n v_n = 0 $$ has only the trivial solution, the columns are independent.

The $i$th row in this equation is $$c_1 + c_2 + \dots + c_{i-1} + c_{i+1} + \dots + c_n = 0,$$ which can equivalently be written as $$c_1 + c_2 + \dots + c_n = c_i.$$

So each of the $c_i$s are equal to their sum, so we have $$c_1=c_2=\dots=c_n,$$ and also $c_i=nc_i$, so we must have $$c_1=c_2=\dots=c_n=0.$$

$\endgroup$
4
$\begingroup$

Let $n\ge 2$ and let $E$ be a $n\times n$ -matrix consisting only of ones. $$E= \begin{pmatrix} 1 & 1 & \ldots & 1 \\ 1 & 1 & \ldots & 1 \\ \ldots & \ldots & \ldots & \ldots \\ 1 & 1 & \ldots & 1 \end{pmatrix} $$ It is easy to notice that $E^2=nE$, i.e., it is a matrix which has $n$ in each position.

We are interested in finding the inverse of the matrix $A=E-I$.

We have $$A^2=(E-I)^2=E^2-2E+I=(n-2)E+I$$

For $n=2$ we get $A^2=I$, which means $A^{-1}=A$. What about $n\ge3$?

Now we can combine the equalities \begin{align*} A&=E-I\\ A^2&=(n-2)E+I \end{align*} to get $$A^2-(n-2)A=(n-1)I$$ which can be rewritten as $$A\cdot (A-(n-2)I) = A\cdot (E-(n-1)I) = (n-1)I.$$

So we see that $$A^{-1} = \frac1{n-1} (E-(n-1)I) = \frac1{n-1} \begin{pmatrix} -(n-2) & 1 & \ldots & 1 \\ 1 & -(n-2) & \ldots & 1 \\ \ldots & \ldots & \ldots & \ldots \\ 1 & 1 & \ldots & -(n-2) \end{pmatrix} $$

We can easily check that product of this matrix with the matrix $A$ is indeed $I$.

Note that a more general approach (which gives the same result for $A^{-1}$) is mentioned in Nick Alger's answer.

It might be also worth mentioning that the inverse is precisely the matrix from this question: Find the inverse of a matrix with a variable

For a generalization of the question from the original post see:

$\endgroup$
2
$\begingroup$

You can certainly expand by minors, but you will have to deal with multiple types of minors. It may be easier to reduce the matrix instead:

  1. Add the 2nd row to the first, the third to the second, and so on, until you add the last row to the second-to-last. What does the matrix look like now?
  2. What do you need to do to the last row to make the matrix upper-triangular?
$\endgroup$
1
$\begingroup$

Alternative "approach": we know that $$\det A = \sum_{\sigma \in S_n} \operatorname{sign}(\sigma) A_{1,\sigma(1)} \cdots A_{n, \sigma(n)}.$$ (In fact, some authors take this as the definition of the determinant.) In our case, $$A_{i, \sigma(i)} = \begin{cases} 0 & \text{ if } i = \sigma(i), \\ 1 & \text{ otherwise,} \end{cases}$$ so $$A_{1,\sigma(1)} \cdots A_{n, \sigma(n)} = \begin{cases} 1 & \text{ if $\sigma$ is a derangement,} \\ 0 & \text{ otherwise.} \end{cases}$$

Therefore, $$\det A = \#\{\text{even derangements of $n$ elements}\}-\#\{\text{odd derangements of $n$ elements}\}.$$

Combinatorialists have formulas for each of the terms above, so you can subtract them. However, apparently these formulas are usually obtained by calculating this determinant using one of the other methods given here! I don't know if there are other ways of getting the same result that (1) avoid this determinant and (2) are easy to understand -- that could be its own question here.

$\endgroup$
0
$\begingroup$

Alternatively, a square matrix is invertible if it's rows are linearly independent. (Of course formally proving this is equal to proving the matrix is invertible for which there are many routes )

I mention this because particularly in this case it is intuitively evident that the rows are independent, e.g. because they have all have one zero in a unique position and you can easily see you get the standard normal basis using the same operation on every row, by taking (1,..,1) minus the rows of your matrix. Formally proving this implies the rows are independent without directly proving the matrix is invertible is probably harder, but interesting on its own.

I'm not sure if an affine transformation always retains the rank of a matrix, but you can also get the same result here with a single linear transformation matrix, i.e. a reflection across the plane $x_1=....x_2$ then negative scaling, but I'd have to work out the specifics.

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