Skip to main content

Subsection 6.3.4 Matrix-vector multiplication

Assume \(A \in \Rmxn \text{,}\) \(x \in \Rn \text{,}\) and \(y \in \Rm\text{.}\) Partition

\begin{equation*} A = \left( \begin{array}{c} \widetilde a_0^T \\ \widetilde a_1^T \\ \vdots \\ \widetilde a_{m-1}^T \end{array} \right) \quad \mbox{and} \quad y = \left( \begin{array}{c} \psi_0 \\ \psi_1 \\ \vdots \\ \psi_{m-1} \end{array} \right). \end{equation*}

Then computing \(y := A x \) can be orchestrated as

\begin{equation} \left( \begin{array}{c} \psi_0 \\ \psi_1 \\ \vdots \\ \psi_{m-1} \end{array} \right) := \left( \begin{array}{c} \widetilde a_0^T x \\ \widetilde a_1^T x\\ \vdots \\ \widetilde a_{m-1}^T x\\ \end{array} \right).\label{chapter06-mv-1}\tag{6.3.4} \end{equation}

From R-1B 6.3.3.2 regarding the dot product we know that

\begin{equation*} \begin{array}{l} \check y = \left( \begin{array}{c} \check \psi_0 \\ \check \psi_1 \\ \vdots \\ \check \psi_{m-1} \end{array} \right) = \left( \begin{array}{c} ( \widetilde a_0 + \delta\!{\widetilde a}_0)^T x \\ ( \widetilde a_1 + \delta\!{\widetilde a}_1)^T x\\ \vdots \\ ( \widetilde a_{m-1} + \delta\!{\widetilde a}_{m-1})^T x\\ \end{array} \right) \\ ~~~= \left( \left( \begin{array}{c} \widetilde a_0^T \\ \widetilde a_1^T\\ \vdots \\ \widetilde a_{m-1}^T \end{array} \right) + \left( \begin{array}{c} \delta\!{\widetilde a}_0^T \\ \delta\!{\widetilde a}_1^T \\ \vdots \\ \delta\!{\widetilde a}_{m-1}^T \end{array} \right) \right) x = ( A + \Delta\!\!A ) x , \end{array} \end{equation*}

where \(\vert \delta\!{\widetilde a}_i \vert \leq \gamma_n \vert \widetilde a_i \vert\text{,}\) \(i = 0, \ldots , m-1 \text{,}\) and hence \(\vert \Delta\!\!A \vert \leq \gamma_n \vert A \vert \text{.}\) .

Also, from Corollary 6.3.3.2 R-1F regarding the dot product we know that

\begin{equation*} \check y = \left( \begin{array}{c} \check \psi_0 \\ \check \psi_1 \\ \vdots \\ \check \psi_{m-1} \end{array} \right) = \left( \begin{array}{c} \widetilde a_0^T x + \delta\!\psi_0\\ \widetilde a_1^T x + \delta\!\psi_1\\ \vdots \\ \widetilde a_{m-1}^T x + \delta\!\psi_{m-1} \end{array} \right) = \left( \begin{array}{c} \widetilde a_0^T \\ \widetilde a_1^T\\ \vdots \\ \widetilde a_{m-1}^T \end{array} \right) x + \left( \begin{array}{c} \delta\!\psi_0 \\ \delta\!\psi_1 \\ \vdots \\ \delta\!\psi_{m-1} \end{array} \right) = A x + \deltay . \end{equation*}

where \(\vert \delta\!\psi_i \vert \leq \gamma_n \vert \widetilde a_i \vert^T \vert x \vert \) and hence \(\vert \deltay \vert \leq \gamma_n \vert A \vert \vert x \vert \text{.}\)

The above observations can be summarized in the following theorem:

Ponder This 6.3.4.1.

In the above theorem, could one instead prove the result

\begin{equation*} \check y = A ( x + \deltax ), \end{equation*}

where \(\deltax \) is "small"?

Solution

The answer is "sort of". The reason is that for each individual element of \(y \)

\begin{equation*} \check \psi_i = \widetilde a_i^T ( x + \deltax ) \end{equation*}

which would appear to support that

\begin{equation*} \left( \begin{array}{c} \check \psi_0 \\ \check \psi_1 \\ \vdots \\ \check \psi_{m-1} \end{array} \right) = \left( \begin{array}{c} \widetilde a_0^T ( x + \deltax ) \\ \widetilde a_1^T ( x + \deltax ) \\ \vdots \\ \widetilde a_{m-1}^T ( x + \deltax ) \end{array} \right). \end{equation*}

However, the \(\deltax \) for each entry \(\check \psi_{i} \) is different, meaning that we cannot factor out \(x + \deltax \) to find that \(\check y = A ( x + \deltax ) \text{.}\)

However, one could argue that we know that \(\check y = A x + \delta\!y \) where \(\vert \deltay \vert \leq \gamma_{n} \vert A \vert \vert x \vert \text{.}\) Hence if \(A \delta\!x = \delta\!y \) then \(A ( x + \deltax ) = \check y \text{.}\) This would mean that \(\delta\!y \) is in the column space of \(A \text{.}\) (For example, if \(A\) is nonsingular). However, that is not quite what we are going for here.

login