Partition Matrices

A block matrix or a partitioned matrix is a matrix that is interpreted as having been broken into sections called blocks or submatrices.

  Partitoned matrices appear in most modern applications of linear algebra because the notation highlights essential structures of matrices. In particular, partitoned matrices play an essential role in the finite element method. Partititoning a matrix is a generalization to used previously a list of columns or rows. Intuitively, a matrix interpreted as a block matrix can be visualized as the original matrix with a collection of horizontal and vertical lines, which break it up, or partition it, into a collection of smaller matrices. Especially when dimensions of a matrix are large, it may be beneficial to view a matrix as combined from smaller submatrices. If we simultaneously partition adjacent rows and adjacent columns of a matrix into groups, this partitions the matrix into submatrices or blocks, resulting in a representation of the matrix as a partitioned or block matrix.

Example: We partition a 4×5 matrix into 6 blocks:
M=[1−23−1431−24−254−3112−342−3]=[1−23−1431−24−254−3112−342−3]=[A11A12A13A21A22A23A31A32A33],
where the block matrices have the following entries:
A11=[1−231],A12=[3−1−24],A13=[4−2],A31=[2−3],A32=[42],A33=[−3].

If matrices A and B are the same size and are partitioned in exactly the same way, then it is natural to make the same partition of the ordinary matrix sum A + B, and sum corresponding blocks. Similarly, one can subtract the partitioned matrices. Multiplication of a partitioned matrix by a scalar is also computed block by block.

  It is possible to use a block partitioned matrix product that involves only algebra on submatrices of the factors. The partitioning of the factors is not arbitrary, however, and requires "conformable partitions" between two matrices A and B such that all submatrix products that will be used are defined in usual row-column rule.

Example: Let
M=[1−23−1431−24−254−3112−342−3]=[1−23−1431−24−254−3112−342−3]=[A11A12A13A21A22A23A31A32A33],B=[6−314−1]=[B1B2B3].
Then their multiplication would be
MB=[A11B1+A12B2+A13B3A21B1+A22B2+A23B3A31B1+A32B2+A33B3],
where
A11B1=[1−231][6−3]=[1215],A12B2=[3−1−24][14]=[−114],A13B3=[4−2][−1]=[−42],
A21B1=[54][6−3]=[18],A22B2=[−31][14]=[1],A23B3=[1][−1]=[−1],
A31B1=[2−3][6−3]=[21],A32B2=[42][14]=[12],A33B3=[−3][−1]=[3].
Combining all terms together, we get
MB=[7311836].
We check calculations with Mathematica:
M = {{ 1, -2, 3, -1, 4},{3, 1, -2, 4, -2},{5, 4, -3, 1, 1},{2, -3, 4, 2, -3}}
B = {{6}, {-3}, {1}, {4}, {-1}}
M.B
Out[1]= {{7}, {31}, {18}, {36}}
Suppose that a (p+q)×(p+q) matrix M can be partitioned into four submatrix blocks as
M=[ABCD],
where both matrices A and D are square matrices of dimensions p×p and q×q, respectively. If A is nonsingular, the Schur complement of M with respect to A is defined as
M/A=D−CA−1B.
If D is nonsingular, the Schur complement of M with respect to D is defined as
M/D=A−BD−1C.

Issai Schur

The Schur complement is named after Issai Schur (1875--1941), who introduced it in 1917 (I. Schur, Potenzreihen im Innern des Einheitskreises, J. Reine Angew. Math., 147, 1917, 205–232). The USA mathematician Emilie Virginia Haynsworth (1916--1985) was the first in 1968 paper to call it the Schur complement. The Schur complement is a key tool in the fields of numerical analysis, statistics and matrix analysis.

  Issai Schur was a Russian mathematician (he was born in Mogilev, now Belarus) who worked in Germany for most of his life. Issai spoke German without a trace of an accent, and nobody even guessed that it was not his first language. He obtained his doctorate in 1901, became lecturer in 1903 and, after a stay at the University of Bonn, professor in 1919. As a student of Ferdinand Georg Frobenius (1849--1917), he worked on group representations. He is perhaps best known today for his result on the existence of the Schur decomposition, which we will discuss later.

  In 1922 Schur was elected to the Prussian Academy, proposed by Planck, the secretary of the Academy. From 1933 events in Germany made Schur's life increasingly difficult. Schur considered himself as a German, not a Jew, but the Nazis had different opinion. Later in 1935 Schur was dismissed from his chair in Berlin but he continued to work there suffering great hardship and difficulties. Schur left Germany for Palestine in 1939, broken in mind and body, having the final humiliation of being forced to find a sponsor to pay the 'Reichs flight tax' to allow him to leave Germany. Without sufficient funds to live in Palestine he was forced to sell his beloved academic books to the Institute for Advanced Study in Princeton.

Example: Consider the matrix
M=[1−23−1431−24−254−3112−342−3]=[1−23−1431−24−254−3112−342−3013−12]=[ABCD],
where
A=[1−231],B=[3−14−242],C=[542−301],D=[−31142−33−12].
Since both square matrices A and D are not singular (detA=7,detD=−30 ), we can evaluate both Schur complements:
M/A=D−CA−1B=17[28−567−321−6732−1424],M/D=A−BD−1C=−13[7194227].
We check calculations with Mathematica:
M = {{1, -2, 3, -1, 4}, {3, 1, -2, 4, -2}, {5, 4, -3, 1, 1}, {2, -3, 4, 2, -3}, {0, 1, 3, -1, 2}}
DD = {{-3, 1, 1}, {4, 2, -3}, {3, -1, 2}}
A = {{1, -2}, {3, 1}}
B = {{3, -1, 4}, {-2, 4, 2}}
CC = {{5, 4}, {2, -3}, {0, 1}}
MA = (DD - CC.Inverse[A].B)*7
Out[6]= {{28, -56, 7}, {-3, 21, -67}, {32, -14, 24}}
MD = (A - B.Inverse[DD].CC)*3
Out[7]= {{-7, -19}, {-42, -27}}

Block Matrix Determinant

For a block matrix M=[ABCD] with square matrices A and D, we have
det(M)=det(A)(M/A)anddet(M)=det(D)(M/D),
provided that inverse matrices exist. The latter follows from the equation
[ABCD][I0−D−1CI]=[A−BD−1CB0D],
where I is the identity matrix (taken to be of the appropriate dimension), and square matrix D is assumed to be nonsingular. Similar formula is valid for invertible matrix A. The following block diagonalization forms learly display the Schur complement role. If A is nonsingular,
[I0−CA−1I][ABCD][I−A−1B0I]=[A00M/A],[ABCD]=[I0CA−1I][A00M/A][IA−1B0I].
If D is nonsingular, we have
[I−BD−10I][ABCD][I0−D−1CI]=[M/D00D],[ABCD]=[IBD−10I][M/D00D][I0D−1CI].

All of these equations can be directly verified by matrix multiplication.

Example: Consider four block matrices:
A1=[3152],A2=[123234],A3=[−112334],A4=[21−1111234].
With Mathematica, we build 5-by-5 matrix from these blockes:
A1 = {{3, 1}, {5, 2}}
A2 = {{1, 2, 3}, {2, 3, 4}}
A3 = {{-1, 1}, {2, 3}, {3, 4}}
A4 = {{2, 1, -1}, {1, 1, 1}, {2, 3, 4}}
M = ArrayFlatten[{{A1, A2}, {A3, A4}}]
M=[A1A2A3A4]=[3112352234−1121−12311134234].
Then we calculate Schur complements
M/A=A4−A3A1−1A2=[134−226−2410],M/D=A1−A2A4−1A3=[202−2].
MA = A4 - A3.Inverse[A1].A2
Out[6]= {{1, 3, 4}, {-2, 2, 6}, {-2, 4, 10}}
Det[MA]
Out[7]= 4
MD = A1 - A2.Inverse[A4].A3
Out[8]= {{2, 0}, {2, -2}}
Det[MD]
Out[9]= -4
Therefore,
detM=detA1det(M/A)=detA4det(M/D)=4.
■

Block Matrix Inversion

To find the inverse matrix to a block matrix M=[ABCD], we have
M−1=[ABCD]−1=[A−1+A−1B(M/A)−1CA−1−A−1B(M/A)−1−(M/A)−1CA−1(M/A)−1],M−1=[ABCD]−1=[(M/D)−1−(M/D)−1BD−1−D−1C(M/D)−1D−1+D−1C(M/D)−1BD−1].
When m = n so that A, B, C, and D are all square, and all of them are nonsingular, one obtains the elegant formula
M−1=[ABCD]−1=[(M/D)−1(M/B)−1(M/C)−1(M/A)−1].
Example: Let us consider a 5-by-5 matrix that is partitioned into four blocks:
M=[ABCD],
where
A=[3512],B=[2−13−112],C=[−321−321],D=[24−63−1118−2−813].
Next we calculate Schur's complements:
M/A=D−CA−1B=[39−25−24−27831−15218],M/D=A−BD−1C=[19/233769].
We check calculations with Mathematica:
A = {{3, 5}, {1, 2}}
B = {{2, -1, 3}, {-1, 1, 2}}
CC = {{-3, 2}, {1, -3}, {2, 1}}
DD= {{2, 4, -6}, {-3, -11, 18}, {-2, -8, 13}}
MA = DD - CC.Inverse[A].B
Out[5]= {{39, -25, -24}, {-27, 8, 31}, {-15, 2, 18}}
MD = A - B.Inverse[DD].CC
Out[6]= {{19/2, 3}, {37, 69}}
Now we calculate components in the inverse matrix (of course, using Mathematica):
Inverse[MD]
Out[7]= {{46/363, -(2/363)}, {-(74/1089), 19/1089}}
Inverse[MA]
Out[8]= {{82/1089, 134/363, -(53/99)}, {7/363, 38/121, -(17/33)}, {2/33, 3/11, -(1/3)}}
-Inverse[MD].B.Inverse[DD]
Out[9]= {{-(109/363), -(4/121), -(4/33)}, {128/1089, -(83/363), 38/99}}
-Inverse[DD].CC.Inverse[MD]
Inverse[DD] + Inverse[DD].CC.Inverse[MD].B.Inverse[DD]
Inverse[A] + Inverse[A].B.Inverse[MA].CC.Inverse[A]
-Inverse[MA].CC.Inverse[A]
-Inverse[A].B.Inverse[MA]
Out[10]= {{395/1089, -(175/1089)}, {47/363, 140/363}, {4/33, 7/33}}
Out[11]= {{82/1089, 134/363, -(53/99)}, {7/363, 38/121, -(17/33)}, {2/33, 3/11, -(1/3)}}
Out[12]= {{46/363, -(2/363)}, {-(74/1089), 19/1089}}
Out[13]= {{395/1089, -(175/1089)}, {47/363, 140/363}, {4/33, 7/33}}
Out[14]= {{-(109/363), -(4/121), -(4/33)}, {128/1089, -(83/363), 38/99}}
Finally, we check the answer:
M = {{3, 5, 2, -1, 3}, {1, 2, -1, 1, 2}, {-3, 2, 2, 4, -6}, {1, -3, 3, -11, 18}, {2, 1, -2, -8, 13}}
Inverse[M]*3501
Out[16]= {{522, -54, -1035, -36, -540}, {304, -179, 524, -249, 544}, {395, -175, 82, 402, -583}, {-291, 1680, -87, 342, -705}, {-222, 1029, 78, 297, -213}}
Therefore,
M−1=13501[522−54−1035−36540304−179524−249544395−17582402−583−2911680−87342−705−222102978297−213].■

Block Diagonal Matrices

A block diagonal matrix is a block matrix that is a square matrix, and having main diagonal blocks square matrices, such that the off-diagonal blocks are zero matrices. A block diagonal matrix M has the form
M=[A10⋯00A2⋯0⋮⋮⋱⋮00⋯An],
where Ak is a square matrix; in other words, it is the direct sum of 1, ... , An: M=A1⊕A2⊕⋯⊕An. It can also be indicated as diag(A1,A2,…,An ). Any square matrix can trivially be considered a block diagonal matrix with only one block.

 

For the determinant and trace, the following properties hold
det(M)=detA1×detA2×⋯×detAn,tr(M)=tr(A1)+tr(A2)+⋯+tr(An).
The inverse of a block diagonal matrix is another block diagonal matrix, composed of the inverse of each block, as follows:
M−1=[A10⋯00A2⋯0⋮⋮⋱⋮00⋯An]−1=[A1−10⋯00A2−1⋯0⋮⋮⋱⋮00⋯An−1].
Example: Suppose we are given two square matrices:
A1=[3152],A4=[21−1111234].
With Mathematica, we build 5-by-5 block diagonal matrix from these two blockes:
A1 = {{3, 1}, {5, 2}}
A4 = {{2, 1, -1}, {1, 1, 1}, {2, 3, 4}}
zero23 = ConstantArray[0, {2, 3}]
zero32 = ConstantArray[0, {3, 2}]
A = ArrayFlatten[{{A1, zero23}, {zero32, A4}}]
A=[A100A4]=[31000520000021−10011100234].
Then we calculate its determinant and determinants of corresponding blocks:
Det[A]
Out[1]= -1
Det[A1]
Out[1]= -1
Det[A4]
Out[1]= 1
which is in accordance with the formula detA=detA1detA2. Finally, we calculate its inverse:
Inverse[A]
Out[4]= {{2, -1, 0, 0, 0}, {-5, 3, 0, 0, 0}, {0, 0, -1, 7, -2}, {0, 0, 2, -10, 3}, {0, 0, -1, 4, -1}}
Inverse[A1]
Out[5]= {{2, -1}, {-5, 3}}
Inverse[A4]
Out[6]= {{-1, 7, -2}, {2, -10, 3}, {-1, 4, -1}}
Therefore,
A−1=[31000520000021−10011100234]−1=[2−1000−5300000−17−2002−10300−14−1].
■

Block Tridiagonal Matrices

A block tridiagonal matrix is another special block matrix, which is just like the block diagonal matrix a square matrix, having square matrices (blocks) in the lower diagonal, main diagonal and upper diagonal, with all other blocks being zero matrices. It is essentially a tridiagonal matrix but has submatrices in places of scalars. A block tridiagonal matrix M has the form
M=[B1C10⋯0A2B2C2⋯0⋮⋱⋱⋱⋮AkBkCk0⋱⋱⋱An−1Bn−1Cn−10⋯AnBn],

where Ak, Bk and Ck are square sub-matrices of the lower, main and upper diagonal respectively.

Example 7: Suppose we are given two square matrices: ■

Product of two block matrices

Suppose that we are given two matrices Am×p and Bp×n that are partitioned as follows:
Am×p=[Er×kFr×p−kGm−r×kHm−r×p−k]andBp×n=[Pk×lQk×n−lRp−k×lSp−k×n−l].
Then their product is
AB=[(EP+FR)r×l(EQ+FS)r×n−l(GP+HR)m−r×l(GQ+HS)m−r×n−l].
Example: Suppose we are given two square matrices: Let
A=[−211−230−101]andB=[−11−10−21−10−32−21].
We find their product by partition these matrices:
A=[EFGH]andB=[PQRS].
■

Direct Sum

For any arbitrary matrices A=[ai,j] (of size n×m ) and B=[bi,j] (of size p×q ), we have the direct sum of A and B, denoted by A⊕B and defined as
A⊕B=[a11⋯a1m0⋯0⋮⋱⋮⋮⋱⋮an,1⋯anm0⋯00⋯0b11⋯b1q⋮⋱⋮⋮⋱⋮0⋯0bp1⋯bpq].

Direct Product

Let A be n-by-m matrix and B be p-by-q matrix, then their Kronecker product or direct product, denoted by A⊗B, is the pn×mq block matrix:
A⊗B=[a11B⋯a1mB⋮⋱⋮an1B⋯anmB].
More explicitly:
A⊗B=[a11b11a11b12⋯a1mb1q⋯⋯a1mb11a1nb12⋯a1mb1qa11b21a11b21⋯a11b2q⋯⋯a1mb21a1mb22⋯a1mb2q⋮⋮⋱⋮⋮⋮⋱⋮a11bp1a11bp2⋯a11bpq⋯⋯a1mbp1a1mbp2⋯a1mbpq⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮an1b11an1b12⋯an1b1q⋯⋯anmb11anmb12⋯anmb1qan1b21an1b22⋯an1b2q⋯⋯anmb21anmb22⋯anmb2q⋮⋮⋱⋮⋮⋮⋱⋮an1bp1an1bp2⋯an1bpq⋯⋯anmbp1anmbp2⋯anmbpq].
The Kronecker product is named after the German mathematician Leopold Kronecker (1823--1891), even though there is little evidence that he was the first to define and use it. Indeed, the Kronecker product should be called the Zehfuss product because Johann Georg Zehfuss (1832--1901) published a paper in 1858 (Zeit. fur Math und Physik, 3, 1858, 298--301), in which he described the matrix operation we now know as the Kronecker product.