Question

Use partitioned matrices to prove by induction that for \(n = 2,3,...\), the \(n \times n\) matrices \(A\) shown below is invertible and \(B\) is its inverse.

\[A = \left[ {\begin{array}{*{20}{c}}1&0&0& \cdots &0\\1&1&0&{}&0\\1&1&1&{}&0\\ \vdots &{}&{}& \ddots &{}\\1&1&1& \ldots &1\end{array}} \right]\]

\[B = \left[ {\begin{array}{*{20}{c}}1&0&0& \cdots &0\\{ - 1}&1&0&{}&0\\0&{ - 1}&1&{}&0\\ \vdots &{}& \ddots & \ddots &{}\\0&{}& \ldots &{ - 1}&1\end{array}} \right]\]

For the induction step, assume A and Bare \(\left( {k + 1} \right) \times \left( {k + 1} \right)\) matrices, and partition Aand B in a form similar to that displayed in Exercises 23.

Short answer

It is proved that by induction, the \(n \times n\) matrices are invertible and \(B\) is their inverse.

Step-by-step solution

Identify partitions A and B in exercise 23

The partition matrices are \({A_1} = \left[ {\begin{array}{*{20}{c}}a&{{0^T}}\\0&A\end{array}} \right],{B_1} = \left[ {\begin{array}{*{20}{c}}b&{{0^T}}\\0&A\end{array}} \right]\).

Here, v and w are in \({\mathbb{R}^k}\); \(A\) and B are \(k \times k\) lower triangular matrices, and \(a\), \(b\) are scalars.

Show by induction that \(n \times n\) matrices A are invertible and B is their inverse

Consider the matrices \[{A_n} = \left[ {\begin{array}{*{20}{c}}1&0&0& \cdots &0\\1&1&0&{}&0\\1&1&1&{}&0\\ \vdots &{}&{}& \ddots &{}\\1&1&1& \ldots &1\end{array}} \right]\] and \[{B_n} = \left[ {\begin{array}{*{20}{c}}1&0&0& \cdots &0\\{ - 1}&1&0&{}&0\\0&{ - 1}&1&{}&0\\ \vdots &{}& \ddots & \ddots &{}\\0&{}& \ldots &{ - 1}&1\end{array}} \right]\].

As a result of direct calculation, \({A_2}{B_2} = {I_2}\). Suppose that for \[{\mathop{\rm n}\nolimits} = k\], the matrix \({A_k}{B_k}\) is \({I_k}\) , and it is written as

\({A_{k + 1}} = \left[ {\begin{array}{*{20}{c}}1&{{0^T}}\\{\mathop{\rm v}\nolimits} &{{A_k}}\end{array}} \right]\)and \({B_{k + 1}} = \left[ {\begin{array}{*{20}{c}}1&{{0^T}}\\{\mathop{\rm v}\nolimits} &{{B_k}}\end{array}} \right]\).

Here, \({\mathop{\rm v}\nolimits} \) and \({\mathop{\rm w}\nolimits} \) are in \({\mathbb{R}^k}\) , \({v^T} = \left[ {\begin{array}{*{20}{c}}1&1&{...}&1\end{array}} \right]\) and \({w^T} = \left[ {\begin{array}{*{20}{c}}{ - 1}&0&{...}&0\end{array}} \right]\). Hence,

\[\begin{array}{c}{A_{k + 1}}{B_{k + 1}} = \left[ {\begin{array}{*{20}{c}}1&{{0^T}}\\{\mathop{\rm v}\nolimits} &{{A_k}}\end{array}} \right]\left[ {\begin{array}{*{20}{c}}1&{{0^T}}\\{\mathop{\rm w}\nolimits} &{{A_k}}\end{array}} \right]\\ = \left[ {\begin{array}{*{20}{c}}{1 + {0^T}{\mathop{\rm w}\nolimits} }&{{0^T} + {0^T}{B_K}}\\{{\mathop{\rm v}\nolimits} + {A_K}{\mathop{\rm w}\nolimits} }&{{\mathop{\rm v}\nolimits} {0^T} + {A_K}{B_K}}\end{array}} \right]\\ = \left[ {\begin{array}{*{20}{c}}1&{{0^T}}\\0&{{I_k}}\end{array}} \right]\\ = {I_{k + 1}}.\end{array}\]

The \(\left( {2,1} \right)\)-entry is 0 since v equals the first column of \({A_k}\). \({A_k}{\mathop{\rm w}\nolimits} \) is \( - 1\) times the first column of \({A_k}\). For all \(n \ge 2\), \({A_n}{B_n} = {I_n}\) according to the principle of induction. The invertible matrix theorem demonstrates that these matrices are invertible because \({A_n}\) and \({B_n}\) are square matrices. Thus, \({B_n} = A_n^{ - 1}\).

Hence, it is proved that by induction, the \(n \times n\) matrices are invertible and \(B\)is their inverse.