Question

In justifying our matrix multiplication algorithm (Section 2.5), we claimed the following block wise property: if X and Y are $\mathit{n}\mathbf{\times }\mathit{n}$n matrices, and

$\mathit{X}\mathbf{=}\left[\begin{array}{cc}A& B\\ C& D\\ & \end{array}\right]\mathbf{,}\mathit{Y}\mathbf{=}\left[\begin{array}{cc}E& F\\ G& H\\ & \end{array}\right]$,

where A,B,C,D,E,F,G, and H are $\mathit{n}\mathbf{/}\mathbf{2}\mathbf{\times }\mathit{n}\mathbf{/}\mathbf{2}$ sub-matrices, then the product XY can be expressed in terms of these blocks:

$\mathit{X}\mathit{Y}\mathbf{=}\left[\begin{array}{cc}A& B\\ C& D\\ & \end{array}\right]\left[\begin{array}{cc}E& F\\ G& H\\ & \end{array}\right]\mathbf{=}\left[\begin{array}{cc}AE+BG& AF+BH\\ CE+DG& CF+DH\\ & \end{array}\right]$

Prove this property.

Short answer

Justification of matrix multiplication

Step-by-step solution

Prove:

Environment multiplication

Allowing the following matrices:

$X=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]$ and $Y=\left[\begin{array}{cc}E& F\\ G& H\end{array}\right]$

X and Y vectors are split into 4 size blocks. $\frac{n}{2}\times \frac{n}{2}$. This combination between X or Y matrix (z) has the following i , j the elements because X and Y were $n\times n$matrices:

_{$Z_{ij}={\sum _{}}_{k=1}{X}_{ik}{Y}_{kj}$} where $1\le i,j\le n$

With each region of both the process of making the product, the specified property may be demonstrated (Z) .

For the sector in which $i,j\le \frac{n}{2}$:

$$\begin{gathered} Z_{ij}={\left(X,Y\right)}_{ij} \\ =\sum _{K=1}^n{X}_{ik}{Y}_{kj} \\ =\sum _{k=1}^n{X}_{ik}{Y}_{kj}+\sum _{K=1}^n{X}_{ik}{Y}_{kj} \\ =\sum _{K=1}^{n/2}{A}_{ik}{E}_{kj}+\sum _{K=1}^{n/2}{B}_{ik}{G}_{kj} \\ ={\left[AE+BG\right]}_{ij} \end{gathered}$$

For the sector in which $i\le \frac{n}{2}$and $\frac{n}{2}\le j\le n$:

$$\begin{gathered} Z_{ij}={\left(XY\right)}_{ij}=\sum _{K=1}^n{X}_{ik}{Y}_{kj} \\ =\sum _{K=1}^n{X}_{ik}{Y}_{kj}+\sum _{n_{k=-+1_{{}_2}}}^n{X}_{ik}{Y}_{kj} \\ =\sum _{K=1}^{n/2}{A}_{ik}{F}_{kj}+\sum _{K=1}^{n/2}{B}_{ik}{H}_{kj} \\ ={\left[AF+BH\right]}_{ij} \end{gathered}$$

For the sector in which $\frac{n}{2}\le i\le n$and $j\le \frac{n}{2}$:

$$\begin{gathered} Z_{ij}={\left(X,Y\right)}_{ij} \\ =\sum _{K=1}^n{X}_{ik}{Y}_{kj} \\ =\sum _{k=1}^n{X}_{ik}{Y}_{kj}+\sum _{K=1}^n{X}_{ik}{Y}_{kj} \\ =\sum _{K=1}^{n/2}{C}_{ik}{E}_{kj}+\sum _{K=1}^{n/2}{D}_{ik}{G}_{kj} \\ ={\left[CE+DG\right]}_{ij} \end{gathered}$$

For the sector in which $\frac{n}{2}\le i,j\le n$ :

$$\begin{gathered} Z_{ij}={\left(X,Y\right)}_{ij} \\ =\sum _{K=1}^n{X}_{ik}{Y}_{kj} \\ =\sum _{k=1}^n{X}_{ik}{Y}_{kj}+\sum _{K=1}^n{X}_{ik}{Y}_{kj} \\ =\sum _{K=1}^{n/2}{C}_{ik}{F}_{kj}+\sum _{K=1}^{n/2}{D}_{ik}{H}_{kj} \\ ={\left[CF+DH\right]}_{ij} \end{gathered}$$

The product of X and Y can be expressed as follows:

$Z=\left[\begin{array}{cc}{Z}_{ij}wherei,j\le \frac{n}{2}& Z_{ij}wherei\le \frac{n}{2}and\frac{n}{2}<j\le n\\ Z_{ij}where\frac{n}{2}<i\le nandj\le \frac{n}{2}& Z_{ij}where\frac{n}{2}<i,j\le n\end{array}\right]$

$Z=\left[\begin{array}{cc}AE+BG& AF+BH\\ CE+DG& CF+DH\\ & \end{array}\right]$

Therefore, the given property is proved.