Matrix Inversion: Partition Method

Introduction

Today we will discuss a not-so-famous method of inverting matrices. This method is recursive in the sense that given a method to find inverse of square matrix of order $n$ it can be applied to find the inverse of a matrix of order $(n + 1)$. This method is named Partition Method or the Escalator Method. The idea is to partition a matrix into smaller sub-matrices and then calculate the inverse from the given inverse of one of the smaller sub-matrices.

Partition Method for Matrix Inversion

Let $A_{n + 1}$ be a matrix of order $(n + 1)$ (i.e. it has $(n + 1)$ rows and the same number of columns). We can express the matrix $A_{n + 1}$ in block form as $$\begin{align} A_{n + 1} &= \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & \vdots & a_{1(n + 1)}\\ a_{21} & a_{22} & \cdots & a_{2n} & \vdots & a_{2(n + 1)}\\ \cdots & \cdots & \cdots & \cdots & \vdots & \cdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} & \vdots & a_{n(n + 1)}\\ \cdots & \cdots & \cdots & \cdots & \vdots & \cdots \\ a_{(n + 1)1} & a_{(n + 1)2} & \cdots & a_{(n + 1)n} & \vdots & a_{(n + 1)(n + 1)}\end{bmatrix}\notag\\ &= \begin{bmatrix}A_{n} & B_{n \times 1} \\ C_{1 \times n} & d\end{bmatrix}\notag\end{align}$$ where $$A_{n} =\begin{bmatrix}a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \cdots & \cdots & \cdots & \cdots\\ a_{n1} & a_{n2} & \cdots & a_{nn}\end{bmatrix}\,\,\, B_{n \times 1} = \begin{bmatrix}a_{1(n + 1)}\\a_{2(n + 1)}\\ \cdots \\ a_{n(n + 1)}\end{bmatrix}$$ $$C_{1\times n} = \begin{bmatrix}a_{(n + 1)1} & a_{(n + 1)2} & \cdots & a_{(n + 1)n}\end{bmatrix}\,\,\, d = a_{(n + 1)(n + 1)}$$ The subscripts used for the matrices above denote their order. Let's now assume that $A_{n}$ is invertible and we also know its inverse. Also let $I$ and $O$ denote identity and zero matrices respectively (their order will be indicated by subscripts). If $A_{n + 1}$ is also invertible then we can write the inverse $A_{n + 1}^{-1}$ in the block form (in the same way as we wrote $A_{n + 1}$) as: $$A_{n + 1}^{-1} = \begin{bmatrix}X_{n} & Y_{n \times 1}\\ Z_{1\times n} & t\end{bmatrix}$$ Now we have $$A_{n + 1}A_{n + 1}^{-1} = I_{n + 1}$$ so that $$\begin{bmatrix}A_{n} & B_{n\times 1}\\ C_{1\times n} & d\end{bmatrix}\begin{bmatrix}X_{n} & Y_{n\times 1}\\ Z_{1\times n} & t\end{bmatrix} = \begin{bmatrix}I_{n} & O_{n\times 1}\\ O_{1\times n} & 1\end{bmatrix}$$ Multiplication above gives the following matrix equations: $$\begin{align} A_{n}X_{n} + B_{n\times 1}Z_{1\times n} &= I_{n}\tag{1}\\ A_{n}Y_{n\times 1} + B_{n\times 1}t &= O_{n\times 1}\tag{2}\\ C_{1\times n}X_{n} + dZ_{1\times n} &= O_{1\times n}\tag{3}\\ C_{1\times n}Y_{n\times 1} + dt &= 1\tag{4}\end{align}$$ From $(2)$ we get $Y_{n\times 1} = - A_{n}^{-1}B_{n\times 1}t$ and putting this in $(4)$ we get $$(-C_{1\times n}A_{n}^{-1}B_{n\times 1} + d)t = 1$$ or $$t = \frac{1}{d - C_{1\times n}A_{n}^{-1}B_{n\times 1}}$$ so that we have $Y_{n\times 1}$ given by $$Y_{n\times 1} = -A_{n}^{-1}B_{n\times 1}t$$ Again from $(1)$ we have $X_{n} = A_{n}^{-1} - A_{n}^{-1}B_{n\times 1}Z_{1\times n}$ and putting this value in $(3)$ we get $$C_{1\times n}A_{n}^{-1} - C_{1\times n}A_{n}^{-1}B_{n\times 1}Z_{1\times n} + dZ_{1\times n} = O_{1\times n}$$ so that $$(d - C_{1\times n}A_{n}^{-1}B_{n\times 1})Z_{1\times n} = -C_{1\times n}A_{n}^{-1}$$ or $$Z_{1\times n} = -C_{1\times n}A_{n}^{-1}t$$ and finally $$X_{n} = A_{n}^{-1}(I_{n} - B_{n\times 1}Z_{1\times n})$$ To aid the memory it makes sense to drop subscripts and then if we have $$\boxed{\displaystyle A_{n + 1} = \begin{bmatrix}A & B \\ C & d\end{bmatrix} = \begin{bmatrix}A & \vdots & B \\ \cdots & \vdots & \cdots \\C & \vdots & d\end{bmatrix}\,\,\, A_{n + 1}^{-1} = \begin{bmatrix}X & Y \\ Z & t\end{bmatrix} = \begin{bmatrix}X & \vdots & Y \\ \cdots & \vdots & \cdots \\Z & \vdots & t\end{bmatrix}}$$ where $A$ is invertible square matrix of order $n$, $B, Y$ are matrices of order $n\times 1$, $C, Z$ are matrices of order $1\times n$, $d, t$ are numbers then $$\boxed{\begin{align} t &= (d - CA^{-1}B)^{-1}\notag\\ Y &= -A^{-1}Bt\notag\\ Z &= -CA^{-1}t\notag\\ X &= A^{-1}(I - BZ)\notag\end{align}}$$ where $I$ is identity matrix of order $n$. Note that if $d = CA^{-1}B$ then the number $t$ is not defined. In this case it can be easily seen that the matrix $A_{n + 1}$ is singular and hence not invertible.

Demonstration of Partition Method

We demonstrate the method by a simple example where $n = 2$ i.e. assuming the inverse of a second order matrix we will calculate the inverse of a third order matrix. Let us then apply this method on the following matrix
$$A_{3} = \begin{bmatrix}1 & 2 & 3\\ 0 & 1 & 4\\ 5 & 6 & 0\end{bmatrix} = \begin{bmatrix}1 & 2 & \vdots & 3\\ 0 & 1 & \vdots & 4\\ \cdots & \cdots & \vdots & \cdots\\ 5 & 6 & \vdots & 0\end{bmatrix} = \begin{bmatrix} A & B\\ C & d\end{bmatrix}$$ Here we have $$A = \begin{bmatrix}1 & 2\\ 0 & 1\end{bmatrix}\,\,\, B = \begin{bmatrix}3\\4\end{bmatrix}\,\,\, C = \begin{bmatrix}5 & 6\end{bmatrix}\,\,\, d = 0$$ Clearly $A$ is invertible as its determinant is $1$ and the inverse is easily found by the adjoint method as $$A^{-1} = \begin{bmatrix}1 & -2\\ 0 & 1\end{bmatrix}$$ We now have $$\begin{align} t &= (d - CA^{-1}B)^{-1}\notag\\ &= \left(0 - \begin{bmatrix}5 & 6\end{bmatrix}\begin{bmatrix}1 & -2\\ 0 & 1\end{bmatrix}\begin{bmatrix}3\\4\end{bmatrix}\right)^{-1}\notag\\ &= \left(\begin{bmatrix}-5 & 4\end{bmatrix}\begin{bmatrix}3\\4\end{bmatrix}\right)^{-1}\notag\\ &= (1)^{-1} = 1\notag\\ Y &= -A^{-1}Bt\notag\\ &= -\begin{bmatrix}1 & -2\\ 0 & 1\end{bmatrix}\begin{bmatrix}3\\4\end{bmatrix}\notag\\ &= \begin{bmatrix}-1 & 2\\ 0 & 1\end{bmatrix}\begin{bmatrix}3\\4\end{bmatrix} = \begin{bmatrix}5 \\ -4\end{bmatrix}\notag\\ Z &= -CA^{-1}t\notag\\ &= -\begin{bmatrix}5 & 6\end{bmatrix}\begin{bmatrix}1 & -2\\ 0 & 1\end{bmatrix} = \begin{bmatrix}-5 & 4\end{bmatrix}\notag\\ X &= A^{-1}(I - BZ)\notag\\ &= \begin{bmatrix}1 & -2\\ 0 & 1\end{bmatrix}\left(\begin{bmatrix}1 & 0\\ 0 & 1\end{bmatrix} - \begin{bmatrix}3\\4\end{bmatrix}\begin{bmatrix}-5 & 4\end{bmatrix}\right)\notag\\ &= \begin{bmatrix}1 & -2\\ 0 & 1\end{bmatrix}\left(\begin{bmatrix}1 & 0\\ 0 & 1\end{bmatrix} - \begin{bmatrix}-15 & 12\\ -20 & 16\end{bmatrix}\right)\notag\\ &= \begin{bmatrix}1 & -2\\ 0 & 1\end{bmatrix}\begin{bmatrix}16 & -12\\ 20 & -15\end{bmatrix} = \begin{bmatrix}-24 & 18\\ 20 & -15\end{bmatrix}\notag\end{align}$$ The final inverse is given by $$A_{3}^{-1} = \begin{bmatrix}X & Y\\ Z & t\end{bmatrix} = \begin{bmatrix}-24 & 18 & \vdots & 5\\ 20 & -15 & \vdots & -4\\ \cdots & \cdots & \vdots & \cdots \\ -5 & 4 & \vdots & 1\end{bmatrix} = \begin{bmatrix}-24 & 18 & 5\\ 20 & -15 & -4\\ -5 & 4 & 1\end{bmatrix}$$ From the above demonstration it should be clear that the above process is not very straightforward nor very efficient. However it is interesting to learn that using this method matrix inversion can be performed by partitioning the given matrix into smaller blocks and this can be suitably programmed for parallel computation.

Print/PDF Version