Skip to main content

Subsection 4.2.1 Partitioned matrix-vector multiplication

Example 4.2.1.1.

Consider

\begin{equation*} \begin{array}{rcl} A = \left( \begin{array}{c | c | c} A_{00} \amp a_{01} \amp A_{02} \\ \hline a_{10}^T \amp \alpha_{11} \amp a_{12}^T \\ \hline A_{20} \amp a_{21} \amp A_{22} \end{array} \right) = \left( \begin{array}{r r | r | r r} -1 \amp 2 \amp 4 \amp 1 \amp 0\\ 1 \amp 0 \amp -1 \amp -2 \amp 1 \\ \hline 2 \amp -1 \amp 3 \amp 1 \amp 2\\ \hline 1 \amp 2 \amp 3 \amp 4 \amp 3 \\ -1 \amp -2 \amp 0 \amp 1 \amp 2 \end{array} \right), \\ x = \left( \begin{array}{c} x_0 \\ \hline \chi_1 \\ \hline x_2 \end{array} \right) = \left( \begin{array}{r} 1 \\ 2\\ \hline 3\\ \hline 4\\ 5 \end{array} \right), \quad \mbox{and} \quad y = \left( \begin{array}{c} y_0 \\ \hline \psi_1 \\ \hline y_2 \end{array} \right) , \end{array} \end{equation*}

where \(y_0, y_2 \in \R^2 \text{.}\) Then \(y = A x \) means that

\begin{equation*} \begin{array}{rcl} y \amp = \amp \left( \begin{array}{c} y_0 \\ \hline \psi_1 \\ \hline y_2 \end{array} \right) = \left( \begin{array}{c | c | c} A_{00} \amp a_{01} \amp A_{02} \\ \hline a_{10}^T \amp \alpha_{11} \amp a_{12}^T \\ \hline A_{20} \amp a_{21} \amp A_{22} \end{array} \right) \left( \begin{array}{c} x_0 \\ \hline \chi_1 \\ \hline x_2 \end{array} \right) = \left( \begin{array}{r c r c r} A_{00} x_0 \amp+\amp a_{01} \chi_1 \amp+\amp A_{02} x_2 \\ \hline a_{10}^T x_0 \amp+\amp \alpha_{11} \chi_1 \amp+\amp a_{12}^T x_2 \\ \hline A_{20} x_0 \amp+\amp a_{21} \chi_1 \amp+\amp A_{22} x_2 \end{array} \right) \\ %%% \amp = \amp %%% \left( \begin{array}{r c r c r} %%% \left( \begin{array}{r r} %%% -1 \amp 2 \\ %%% 1 \amp 0 %%% \end{array} %%% \right) %%% \left( \begin{array}{r} %%% 1 \\ %%% 2 %%% \end{array} %%% \right) %%% \amp+\amp %%% \left( \begin{array}{r} %%% 4 \\ %%% -1 %%% \end{array} %%% \right) %%% 3 %%% \amp+\amp %%% \left( \begin{array}{r r} %%% 1 \amp 0 \\ %%% -2 \amp 1 %%% \end{array} %%% \right) %%% \left( \begin{array}{r} %%% 4 \\ %%% 5 %%% \end{array} %%% \right) \\ \hline %%% % %%% \left( \begin{array}{r r} %%% 2 \amp -1 %%% \end{array} %%% \right) %%% \left( \begin{array}{r} %%% 1 \\ %%% 2 %%% \end{array} %%% \right) %%% \amp+\amp %%% \left(\begin{array}{c} 3 \end{array}\right) %%% 3 %%% \amp+\amp %%% \left( \begin{array}{r r} %%% 1 \amp 2 %%% \end{array} %%% \right) %%% \left( \begin{array}{r} %%% 4 \\ %%% 5 %%% \end{array} %%% \right) \\ \hline %%% % %%% \left( \begin{array}{r r} %%% 1 \amp 2 \\ %%% -1 \amp -2 %%% \end{array} %%% \right) %%% \left( \begin{array}{r} %%% 1 \\ %%% 2 %%% \end{array} %%% \right) %%% \amp+\amp %%% \left( \begin{array}{r} %%% 3 \\ %%% 0 %%% \end{array} %%% \right) %%% 3 %%% \amp+\amp %%% \left( \begin{array}{r r} %%% 4 \amp 3 \\ %%% 1 \amp 2 %%% \end{array} %%% \right) %%% \left( \begin{array}{r} %%% 4 \\ %%% 5 %%% \end{array} %%% \right) %%% \end{array} %%% \right) %%% \\ %%% \amp = \amp %%% \left( \begin{array}{c} %%% \left( \begin{array}{r} %%% 3 \\ %%% 1 %%% \end{array} %%% \right) %%% + %%% \left( \begin{array}{r} %%% 12 \\ %%% -3 %%% \end{array} %%% \right) %%% + %%% \left( \begin{array}{r} %%% 4 \\ %%% -3 %%% \end{array} %%% \right) \\ \hline %%% % %%% 0 %%% + %%% 9 %%% + %%% 14\\ \hline %%% % %%% \left( \begin{array}{r} %%% 5 \\ %%% -5 %%% \end{array} %%% \right) %%% + %%% \left( \begin{array}{r} %%% 9 \\ %%% 0 %%% \end{array} %%% \right) %%% + %%% \left( \begin{array}{r} %%% 31 \\ %%% 14 %%% \end{array} %%% \right) %%% \end{array} %%% \right) %%% = %%% \left( \begin{array}{r} %%% 19 \\ %%% -5 \\ \hline %%% 23 \\ \hline %%% 45 \\ %%% 9 %%% \end{array} %%% \right) \end{array} \end{equation*}

%%%

\begin{equation*} \begin{array}{rcl} \amp = \amp \left( \begin{array}{r c r c r} \left( \begin{array}{r r} -1 \amp 2 \\ \color{red} 1\amp \color{red} 0 \end{array} \right) \left( \begin{array}{r} \color{red} 1 \\ \color{red} 2 \end{array} \right) \amp+\amp \left( \begin{array}{r} 4 \\ {\color{red} -1} \end{array} \right) \color{red} 3 \amp+\amp \left( \begin{array}{r r} 1 \amp 0 \\ \color{red}{ -2} \amp \color{red} 1 \end{array} \right) \left( \begin{array}{r} \color{red} 4 \\ \color{red} 5 \end{array} \right) \\ \hline % \left( \begin{array}{r r} 2 \amp -1 \end{array} \right) \left( \begin{array}{r} 1 \\ 2 \end{array} \right) \amp+\amp \left( \begin{array}{c} 3 \end{array} \right) 3 \amp+\amp \left( \begin{array}{r r} 1 \amp 2 \end{array} \right) \left( \begin{array}{r} 4 \\ 5 \end{array} \right) \\ \hline % \left( \begin{array}{r r} 1 \amp 2 \\ -1 \amp -2 \end{array} \right) \left( \begin{array}{r} 1 \\ 2 \end{array} \right) \amp+\amp \left( \begin{array}{r} 3 \\ 0 \end{array} \right) 3 \amp+\amp \left( \begin{array}{r r} 4 \amp 3 \\ 1 \amp 2 \end{array} \right) \left( \begin{array}{r} 4 \\ 5 \end{array} \right) \end{array} \right) =\\ \amp \amp \left( \begin{array}{r @{} c @{} r @{} c @{} r} \left( \begin{array}{r r} (-1) \times (1) + (2) \times (2) \\ \color{red}{ (1) \times (1) + (0) \times (2)} \\ \end{array} \right) \amp+\amp \left( \begin{array}{r} (4) \times (3) \\ \color{red}{ (-1) \times (3)} \end{array} \right) \amp+\amp \left( \begin{array}{r r} (1) \times (4) + (0) \times (5) \\ \color{red}{ (-2) \times (4) + (1) \times (5) } \end{array} \right) \\ \hline % (2) \times (1) + (-1) \times (2) \amp+\amp (3) \times (3) \amp+\amp (1) \times (4) + (2) \times (5) \\ \hline % \left( \begin{array}{r r} (1) \times (1) + (2) \times (2) \\ (-1) \times (1) + (-2) \times (2) \end{array} \right) \amp+\amp \left( \begin{array}{r} (3) \times 3 \\ (0) \times 3 \end{array} \right) \amp+\amp \left( \begin{array}{r r} (4) \times (4) + (3) \times (5)\\ (1) \times (4) + (2) \times (5) \end{array} \right) \end{array} \right) = \\ \amp \amp \begin{MatrixC} (-1) \times (1) + (2) \times (2) + (4) \times (3) + (1) \times (4) + (0) \times (5) \\ \color{red}{ (1) \times (1) + (0) \times (2) + (-1) \times (3) + (-2) \times (4) + (1) \times (5)} \\ \hline (2) \times (1) + (-1) \times (2) + (3) \times (3) + (1) \times (4) + (2) \times (5) \\ \hline (1) \times (1) + (2) \times (2) + (3) \times (3) + (4) \times (4) + (3) \times (5) \\ (-1) \times (1) + (-2) \times (2) + (0) \times (3) + (1) \times (4) + (2) \times (5) \end{MatrixC} = \left( \begin{array}{r} 19 \\ \color{red}{-5} \\ \hline 23 \\ \hline 45 \\ 9 \end{array} \right) \end{array} \end{equation*}

Above, it helps to track the values and calculations highlighted in red.

Homework 4.2.1.1.

Consider

\begin{equation*} A = \left( \begin{array}{r r r r r} -1 \amp 2 \amp 4 \amp 1 \amp 0\\ 1 \amp 0 \amp -1 \amp -2 \amp 1 \\ 2 \amp -1 \amp 3 \amp 1 \amp 2\\ 1 \amp 2 \amp 3 \amp 4 \amp 3 \\ -1 \amp -2 \amp 0 \amp 1 \amp 2 \end{array} \right) \quad \mbox{and} \quad x = \left( \begin{array}{r} 1 \\ 2\\ 3\\ 4\\ 5 \end{array} \right), \end{equation*}

and partition these into submatrices (regions) as follows:

\begin{equation*} \left( \begin{array}{c | c | c} A_{00} \amp a_{01} \amp A_{02} \\ \hline a_{10}^T \amp \alpha_{11} \amp a_{12}^T \\ \hline A_{20} \amp a_{21} \amp A_{22} \end{array} \right) \quad \mbox{and} \quad \left( \begin{array}{c} x_0 \\ \hline \chi_1 \\ \hline x_2 \end{array} \right), \end{equation*}

where \(A_{00} \in \R^{3x3} \text{,}\) \(x_{0} \in \R^3 \text{,}\) \(\alpha_{11} \) is a scalar, and \(\chi_1 \) is a scalar. Show with lines how \(A \) and \(x \) are partitioned:

\begin{equation*} \left( \begin{array}{r r r r r} -1 \amp 2 \amp 4 \amp 1 \amp 0\\ 1 \amp 0 \amp -1 \amp -2 \amp 1 \\ 2 \amp -1 \amp 3 \amp 1 \amp 2\\ 1 \amp 2 \amp 3 \amp 4 \amp 3 \\ -1 \amp -2 \amp 0 \amp 1 \amp 2 \end{array} \right) \quad \quad \left( \begin{array}{r} 1 \\ 2\\ 3\\ 4\\ 5 \end{array} \right). \end{equation*}
Solution
\begin{equation*} \left( \begin{array}{r r r | r | r} -1 \amp 2 \amp 4 \amp 1 \amp 0\\ 1 \amp 0 \amp -1 \amp -2 \amp 1 \\ 2 \amp -1 \amp 3 \amp 1 \amp 2\\ \hline 1 \amp 2 \amp 3 \amp 4 \amp 3 \\ \hline -1 \amp -2 \amp 0 \amp 1 \amp 2 \end{array} \right) \quad \quad \left( \begin{array}{r} 1 \\ 2\\ 3\\ \hline 4\\ \hline 5 \end{array} \right). \end{equation*}
Homework 4.2.1.2.

With the partitioning of matrices \(A \) and \(x \) in the above exercise, repeat the partitioned matrix-vector multiplication, similar to the calculation in Example 4.2.1.1.

Solution
\begin{equation*} \begin{array}{rcl} y \amp = \amp \left( \begin{array}{c} y_0 \\ \hline \psi_1 \\ \hline y_2 \end{array} \right) = \left( \begin{array}{c | c | c} A_{00} \amp a_{01} \amp A_{02} \\ \hline a_{10}^T \amp \alpha_{11} \amp a_{12}^T \\ \hline A_{20} \amp a_{21} \amp A_{22} \end{array} \right) \left( \begin{array}{c} x_0 \\ \hline \chi_1 \\ \hline x_2 \end{array} \right) \\ \amp = \amp \left( \begin{array}{r c r c r} A_{00} x_0 \amp+\amp a_{01} \chi_1 \amp+\amp A_{02} x_2 \\ \hline a_{10}^T x_0 \amp+\amp \alpha_{11} \chi_1 \amp+\amp a_{12}^T x_2 \\ \hline A_{20} x_0 \amp+\amp a_{21} \chi_1 \amp+\amp A_{22} x_2 \end{array} \right) \\ \amp = \amp \left( \begin{array}{r c r c r} \left( \begin{array}{r r r} -1 \amp 2 \amp 4\\ 1\amp 0 \amp -1 \\ 2 \amp -1 \amp 3 \end{array} \right) \left( \begin{array}{r} 1 \\ 2 \\ 3 \end{array} \right) \amp+\amp \left( \begin{array}{r} 1 \\ -2 \\ 1 \end{array} \right) 4 \amp+\amp \left( \begin{array}{r r} 0 \\ 1 \\ 2 \end{array} \right) 5 \\ \hline % \left( \begin{array}{r r r} 1 \amp 2 \amp 3 \end{array} \right) \left( \begin{array}{r} 1 \\ 2 \\ 3 \end{array} \right) \amp+\amp \left( \begin{array}{c} 4 \end{array} \right) 4 \amp+\amp \left( \begin{array}{r r} 3 \end{array} \right) \left( \begin{array}{r} 5 \end{array} \right) \\ \hline % \left( \begin{array}{r r r} -1 \amp -2 \amp 0 \end{array} \right) \left( \begin{array}{r} 1 \\ 2 \\ 3 \end{array} \right) \amp+\amp \left( \begin{array}{r} 1 \end{array} \right) 4 \amp+\amp \left( \begin{array}{r r r} 2 \end{array} \right) 5 \end{array} \right) =\\ %%% \amp \amp \left( \begin{array}{r @{} c @{} r @{} c @{} r @{} c @{} r} \left( \begin{array}{r r} (-1) \times (1) + (2) \times (2) + (4) \times (3)\\ (1) \times (1) + (0) \times (2) + (-1) \times (3)\\ (2) \times (1) + (-1) \times (2) + (3) \times (3)\\ \end{array} \right) \amp+\amp \left( \begin{array}{r} (1) \times (4) \\ (-2) \times (4) \\ (1) \times (4) \end{array} \right) \amp+\amp \left( \begin{array}{r r} (0) \times (5) \\ (1) \times (5) \\ (2) \times (5) \\ \end{array} \right) \\ \hline % (1) \times (1) + (2) \times (2) + ( 3 ) \times ( 3 ) \amp+\amp (4) \times (4) \amp+\amp (3) \times (5) \\ \hline % (-1) \times (1) + (-2) \times (2) + (0) \times (3) \amp+\amp (1) \times (4) \amp+\amp (2) \times (5) \end{array} \right) = \\ \amp \amp \begin{MatrixC} (-1) \times (1) + (2) \times (2) + (4) \times (3) + (1) \times (4) + (0) \times (5) \\ (1) \times (1) + (0) \times (2) + (-1) \times (3) + (-2) \times (4) + (1) \times (5) \\ (2) \times (1) + (-1) \times (2) + (3) \times (3) + (1) \times (4) + (2) \times (5) \\ \hline (1) \times (1) + (2) \times (2) + (3) \times (3) + (4) \times (4) + (3) \times (5) \\ \hline (-1) \times (1) + (-2) \times (2) + (0) \times (3) + (1) \times (4) + (2) \times (5) \end{MatrixC} \\ \amp = \amp \left( \begin{array}{r} 19 \\ -5 \\ 23 \\ \hline 45 \\ \hline 9 \end{array} \right) \end{array} \end{equation*}

The insights regarding partitioned matrix-vector multiplication can be generalized: Let \(A \in \Rmxn \text{,}\) \(x \in \Rn \text{,}\) and \(y \in \Rm \text{.}\) Partition

\begin{equation*} A = \left( \begin{array}{ c | c | c | c } A_{0,0} \amp A_{0,1} \amp \cdots \amp A_{0,N-1} \\ \hline A_{1,0} \amp A_{1,1} \amp \cdots \amp A_{1,N-1} \\ \hline \vdots \amp \vdots \amp \ddots \amp \vdots \\ \hline A_{M-1,0} \amp A_{M-1,1} \amp \cdots \amp A_{M-1,N-1} \end{array} \right), \quad x = \left( \begin{array}{ c } x_0 \\ \hline x_1 \\ \hline \vdots \\ \hline x_{N-1} \end{array} \right),\quad \mbox{and} \quad y = \left( \begin{array}{ c } y_0 \\ \hline y_1 \\ \hline \vdots \\ \hline y_{M-1} \end{array} \right) \end{equation*}

where

  • \(m = m_0 + m_1 + \cdots + m_{M-1} \text{,}\)

  • \(m_i \geq 0 \) for \(i = 0, \ldots, M-1 \text{,}\)

  • \(n = n_0 + n_1 + \cdots + n_{N-1} \text{,}\)

  • \(n_j \geq 0 \) for \(j = 0, \ldots, N-1 \text{,}\) and

  • \(A_{i,j} \in \R^{m_i \times n_j} \text{,}\) \(x_{j} \in \R^{n_j} \text{,}\) and \(y_{i} \in \R^{m_i} \text{.}\)

If \(y = A x \) then

\begin{equation*} \begin{array}{l} \left( \begin{array}{ c | c | c | c } A_{0,0} \amp A_{0,1} \amp \cdots \amp A_{0,N-1} \\ \hline A_{1,0} \amp A_{1,1} \amp \cdots \amp A_{1,N-1} \\ \hline \vdots \amp \vdots \amp \ddots \amp \vdots \\ \hline A_{M-1,0} \amp A_{M-1,1} \amp \cdots \amp A_{M-1,N-1} \end{array} \right) \left( \begin{array}{ c } x_0 \\ \hline x_1 \\ \hline \vdots \\ \hline x_{N-1} \end{array} \right) \\ ~~~~~~~~~~ = \begin{MatrixC} A_{0,0} x_{0} + A_{0,1} x_{1} + \cdots + A_{0,N-1} x_{N-1} \\ \hline A_{1,0} x_{0} + A_{1,1} x_{1} + \cdots + A_{1,N-1} x_{N-1} \\ \hline \vdots \\ \hline A_{M-1,0} x_{0} + A_{M-1,1} x_{1} + \cdots + A_{M-1,N-1} x_{N-1} \end{MatrixC}. \end{array} \end{equation*}

In other words,

\begin{equation*} y_{i} = \sum_{j=0}^{N-1} A_{i,j} x_{j} . \end{equation*}

This is intuitively true and messy to prove carefully. Therefore we will not give its proof, relying on the many examples we will encounter in subsequent units instead.

Remark 4.2.1.2.

If one partitions matrix \(A \text{,}\) vector \(x \text{,}\) and vector \(y \) into blocks, and one makes sure the dimensions match up, then blocked matrix-vector multiplication proceeds exactly as does a regular matrix-vector multiplication except that individual multiplications of scalars commute while (in general) individual multiplications with matrix and vector blocks (submatrices and subvectors) do not.

Remark 4.2.1.3.

The labeling of the submatrices and subvectors in this unit was carefully chosen to convey information. Consider

\begin{equation*} A = \left( \begin{array}{c | c | c} A_{00} \amp a_{01} \amp A_{02} \\ \hline a_{10}^T \amp \alpha_{11} \amp a_{12}^T \\ \hline A_{20} \amp a_{21} \amp A_{22} \end{array} \right) \end{equation*}

The letters that are used convey information about the shapes. For example, for \(a_{01} \) and \(a_{21} \) the use of a lowercase Roman letter indicates they are column vectors while the \(\phantom{~}^T \)s in \(a_{10}^T \) and \(a_{12}^T \) indicate that they are row vectors. Symbols \(\alpha_{11} \) and \(\chi_1 \) indicate these are scalars. We will use these conventions consistently to enhance readability.

Remark 4.2.1.4.

Notice that the partitioning of matrix \(A \) and vectors \(x \) and \(y\) has to be "conformal". The simplest way to understand this is that matrix-vector multiplication only works if the sizes of matrices and vectors being multiply match. So, a partitioning of \(A \text{,}\) \(x \text{,}\) and \(y \text{,}\) when performing a given operation, is conformal if the suboperations with submatrices and subvectors that are encountered make sense.

login