Matrix Inversion: Partition Method

3 comments

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

3 comments :: Matrix Inversion: Partition Method

Post a Comment

  1. From Karan (comment on http://paramanands.wordpress.com/2012/08/19/matrix-inversion-partition-method/):
    ------------

    Sir, I would really appreciate your demonstrating the solution of a 5*5 matrix by this method. Are we supposed to use the inverse of the 3*3 matrix to find inverse of the 4*4 matrix which could be further used for finding the inverse of 5*5 matrix? How is that done? When we put the matrix 'X' so as to find inv(5*5), we're required to calculate the inverse of 'X', right?

    My Reply:
    ---------

    Hello Karan,
    If you observe the example carefully you will see that we have started with the inverse of 2x2 matrix and then using this found inverse of 3x3 matrix. Now repeating the same procedure we can find inverse of 4x4 matrix using the already obtained inverse of 3x3 matrix. Repeating further we can get the inverse of 5x5 matrix.

    I can not provide all the calculations, as it will be lengthy but I will provide a sample example:

    Let $\displaystyle A_{5} = \begin{bmatrix} a & b & c & d & e\\
    f & g & h & i & j\\
    k & l & m & n & o\\
    p & q & r & s & t\\
    u & v & w & x & y\end{bmatrix}$

    Then we first find the inverse of
    $\displaystyle A_{2} = \begin{bmatrix} a & b \\ f & g\end{bmatrix}$
    Next we find inverse of
    $\displaystyle A_{3} = \begin{bmatrix} a & b & c \\ f & g & h \\ k & l & m \end{bmatrix}$
    Then we find inverse of
    $\displaystyle A_{4} = \begin{bmatrix} a & b & c & d\\ f & g & h & i \\ k & l & m & n \\ p & q & r & s\end{bmatrix}$
    and then finally the inverse of $A_{5}$.

    In each step the inverse calculated from previous step is used.

  2. There's another description here (using different symbols):
    Partition method (Escalator Method) of finding the inverse of a Matrix
    http://mathumatiks.com/index.php?module=subpage&nid=268

  3. Really helpful.
    Thanks for sharing sirji :)