## Linear Algebra and Its Applications, Review Exercise 1.6

Review exercise 1.6. (a) For each of the each of the 2 by 2 matrices containing only 0 or 1 as entries, determine whether the matrix is invertible or not. (b) Of the 10 by 10 matrices containing only 0 or 1 as entries, is a particular matrix chosen at random more likely to be invertible or not?

Answer: (a) A 2 by 2 matrix has four entries. If each entry can be either 0 or 1 then there are 16 possible matrices of this type: $A_0 = \begin{bmatrix} 0&0 \\ 0&0 \end{bmatrix} \quad A_1 = \begin{bmatrix} 0&0 \\ 0&1 \end{bmatrix} \quad A_2 = \begin{bmatrix} 0&1 \\ 0&0 \end{bmatrix} \quad A_3 = \begin{bmatrix} 0&1 \\ 0&1 \end{bmatrix}$ $A_4 = \begin{bmatrix} 0&0 \\ 1&0 \end{bmatrix} \quad A_5 = \begin{bmatrix} 0&0 \\ 1&1 \end{bmatrix} \quad A_6 = \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix} \quad A_7 = \begin{bmatrix} 0&1 \\ 1&1 \end{bmatrix}$ $A_8 = \begin{bmatrix} 1&0 \\ 0&0 \end{bmatrix} \quad A_9 = \begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix} \quad A_{10} = \begin{bmatrix} 1&1 \\ 0&0 \end{bmatrix} \quad A_{11} = \begin{bmatrix} 1&1 \\ 0&1 \end{bmatrix}$ $A_{12} = \begin{bmatrix} 1&0 \\ 1&0 \end{bmatrix} \quad A_{13} = \begin{bmatrix} 1&0 \\ 1&1 \end{bmatrix} \quad A_{14} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \quad A_{15} = \begin{bmatrix} 1&1 \\ 1&1 \end{bmatrix}$

Of these matrices, the following ten matrices are singular: $A_0, A_1, A_2, A_3, A_4, A_5, A_8, A_{10}, A_{12}, A_{15}$

This can be most easily shown by computing the value $ad - bc$, which is zero for all these matrices.

The remaining six matrices are nonsingular and have inverses as follows: $A_{6}^{-1} = \frac{1}{0 \cdot 0 - 1 \cdot 1} \begin{bmatrix} 0&-1 \\ -1&0 \end{bmatrix} = \frac{1}{-1} \begin{bmatrix} 0&-1 \\ -1&0 \end{bmatrix} = \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix} = A_{6}$ $A_{7}^{-1} = \frac{1}{0 \cdot 1 - 1 \cdot 1} \begin{bmatrix} 1&-1 \\ -1&0 \end{bmatrix} = \frac{1}{-1} \begin{bmatrix} 1&-1 \\ -1&0 \end{bmatrix} = \begin{bmatrix} -1&1 \\ 1&0 \end{bmatrix}$ $A_{9}^{-1} = I^{-1} = I = A_{9}$ $A_{11}^{-1} = \frac{1}{1 \cdot 1 - 1 \cdot 0} \begin{bmatrix} 1&-1 \\ 0&1 \end{bmatrix} = \frac{1}{1} \begin{bmatrix} 1&-1 \\ 0&1 \end{bmatrix} = \begin{bmatrix} 1&-1 \\ 0&1 \end{bmatrix}$ $A_{13}^{-1} = \frac{1}{1 \cdot 1 - 0 \cdot 1} \begin{bmatrix} 1&0 \\ -1&1 \end{bmatrix} = \frac{1}{1} \begin{bmatrix} 1&0 \\ -1&1 \end{bmatrix} = \begin{bmatrix} 1&0 \\ -1&1 \end{bmatrix}$ $A_{14}^{-1} = \frac{1}{1 \cdot 0 - 1 \cdot 1} \begin{bmatrix} 0&-1 \\ -1&1 \end{bmatrix} = \frac{1}{-1} \begin{bmatrix} 0&-1 \\ -1&1 \end{bmatrix} = \begin{bmatrix} 0&1 \\ 1&-1 \end{bmatrix}$

(b) The 10 by 10 matrices have 100 entries, and if each can be 0 or 1 that means there are $2^{100}$ possible matrices of this type. At present I don’t know of a good method to determine whether the majority of those matrices are invertible or not. I’ll update this post later if and when I have time to work on this some more.

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition , Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books .

This entry was posted in linear algebra. Bookmark the permalink.