Ch 1.4 The Matrix Equation Ax = b

1.4 The Matrix Equation $Ax = b$

Equivalence of System, Vector, and Matrix Equations

Connection to Span (from Section 1.3)

• A vector equation is equivalent to a system of linear equations.

• Example (Page 1): A system involving a vector $y$ and vectors ${V1, V2, V3}$ can be represented by an augmented matrix.

  • Row reduction of the augmented matrix:
    $\begin{bmatrix} 1 & 5 & -3 & -4 \ -2 & -7 & 0 & h \ 3 & -6 & -5 & -8 \ \end{bmatrix} \sim \begin{bmatrix} 1 & 5 & -3 & -4 \ 0 & 1 & -2 & -1 \ 0 & 0 & 1 & h-5 \ \end{bmatrix}$

  • The system is consistent if and only if there's no pivot in the last (fourth) column. This means $(h-5)$ must be zero.

  • Therefore, $y$ is in $Span{V1, V2, V3}$ if and only if $h = 5$.

• Important Note: The presence of a free variable does not guarantee that a system is consistent.

Linear Combinations and Span Properties

• If vectors $u$ and $v$ are in $Span{W1, W2, W3}$, then there exist scalars $C1, C2, C3$ and $d1, d2, d3$ such that:

  • $u = C1W1 + C2W2 + C3W3$

  • $v = d1W1 + d2W2 + d3W3$

• Then, their sum $u + v$ is also in $Span{W1, W2, W3}$:

  • $u + v = (C1W1 + C2W2 + C3W3) + (d1W1 + d2W2 + d3W3)$

  • $u + v = (C1 + d1)W1 + (C2 + d2)W2 + (C3 + d3)W3$

  • Since $(C1 + d1)$, $(C2 + d2)$, and $(C3 + d3)$ are also scalars, this shows $u + v$ is a linear combination of ${W1, W2, W3}$.

Definition of the Matrix-Vector Product $Ax$

• A fundamental idea in linear algebra is to view a linear combination of vectors as the product of a matrix and a vector.

• Definition (Page 1): If $A$ is an $m \times n$ matrix with columns $a1, \dots, an$, and if $x$ is in $R^n$ (a column vector with $n$ entries), then the product of $A$ and $x$, denoted by $Ax$, is the linear combination of the columns of $A$ using the corresponding entries in $x$ as weights.

  • $Ax = \begin{bmatrix} a1 & a2 & \dots & an \end{bmatrix} \begin{bmatrix} x1 \ x2 \ \vdots \ xn \end{bmatrix} = x1a1 + x2a2 + \dots + xnan$

• Condition: $Ax$ is defined only if the number of columns of $A$ (which is $n$) equals the number of entries in $x$ (also $n$).

• Example 1 (Page 1):

  • a.
    $\begin{bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \ \end{bmatrix} \begin{bmatrix} 4 \ 3 \ 7 \ \end{bmatrix} = 4 \begin{bmatrix} 1 \ 4 \ \end{bmatrix} + 3 \begin{bmatrix} 2 \ 5 \ \end{bmatrix} + 7 \begin{bmatrix} 3 \ 6 \ \end{bmatrix} = \begin{bmatrix} 4 \ 16 \ \end{bmatrix} + \begin{bmatrix} 6 \ 15 \ \end{bmatrix} + \begin{bmatrix} 21 \ 42 \ \end{bmatrix} = \begin{bmatrix} 31 \ 73 \ \end{bmatrix}$

  • b.
    $\begin{bmatrix} 8 & 3 \ 5 & 1 \ \end{bmatrix} \begin{bmatrix} 4 \ 7 \ \end{bmatrix} = 4 \begin{bmatrix} 8 \ 5 \ \end{bmatrix} + 7 \begin{bmatrix} 3 \ 1 \ \end{bmatrix} = \begin{bmatrix} 32 \ 20 \ \end{bmatrix} + \begin{bmatrix} 21 \ 7 \ \end{bmatrix} = \begin{bmatrix} 53 \ 27 \ \end{bmatrix}$

• Example 2 (Page 2): To write the linear combination $3v1 - 5v2 + 7v3$ as a matrix times a vector:

  • Place the vectors $v1, v2, v3$ into the columns of a matrix $A$.

  • Place the weights $3, -5, 7$ into a vector $x$.

  • Thus, $3v1 - 5v2 + 7v3 = \begin{bmatrix} v1 & v2 & v3 \end{bmatrix} \begin{bmatrix} 3 \ -5 \ 7 \ \end{bmatrix} = Ax$

The Matrix Equation $Ax = b$

• Any system of linear equations can be written as an equivalent matrix equation in the form $Ax = b$.

• Example (System to Matrix Equation, Page 2):

  • System of linear equations:
    $x1 - 2x2 - x3 = 4$
    $-5x2 + 3x3 = 1$

  • Equivalent vector equation:
    $x1 \begin{bmatrix} 1 \ 0 \ \end{bmatrix} + x2 \begin{bmatrix} -2 \ -5 \ \end{bmatrix} + x3 \begin{bmatrix} -1 \ 3 \ \end{bmatrix} = \begin{bmatrix} 4 \ 1 \ \end{bmatrix}$

  • Equivalent matrix equation:
    $\begin{bmatrix} 1 & -2 & -1 \ 0 & -5 & 3 \ \end{bmatrix} \begin{bmatrix} x1 \ x2 \ x3 \ \end{bmatrix} = \begin{bmatrix} 4 \ 1 \ \end{bmatrix}$

  • The matrix here is the coefficient matrix of the system.

Theorem 3 (Page 2): Equivalence of Three Forms

• If $A$ is an $m \times n$ matrix with columns $a1, \dots, an$, and $b$ is in $R^m$, then the matrix equation $Ax = b$ has the same solution set as:

  • The vector equation: $x1a1 + x2a2 + \dots + xnan = b$

  • The system of linear equations whose augmented matrix is:
    $\begin{bmatrix} a1 & a2 & \dots & an & b \ \end{bmatrix}$

• Significance: This theorem provides a powerful tool, allowing problems to be viewed in three equivalent ways: as a matrix equation, a vector equation, or a system of linear equations. This flexibility aids in constructing mathematical models and solving problems through row reduction of the augmented matrix.

Existence of Solutions

• Key Fact (Page 3): The equation $Ax = b$ has a solution if and only if $b$ is a linear combination of the columns of $A$. Equivalently, $Ax = b$ is consistent if and only if $b$ is in $Span{a1, \dots, an}$.

Determining Consistency for All Possible $b$

• Example 3 (Page 3): Let $A = \begin{bmatrix} 1 & 3 & 4 \ -4 & 2 & -6 \ -3 & -2 & -7 \ \end{bmatrix}$. Is the equation $Ax = b$ consistent for all possible $b = \begin{bmatrix} b1 \ b2 \ b3 \ \end{bmatrix}$?

  • Row reduce the augmented matrix $[A \ b]$:
    $\begin{bmatrix} 1 & 3 & 4 & b1 \ -4 & 2 & -6 & b2 \ -3 & -2 & -7 & b3 \ \end{bmatrix} \sim \begin{bmatrix} 1 & 3 & 4 & b1 \ 0 & 14 & 10 & b2+4b1 \ 0 & 7 & 5 & b3+3b1 \ \end{bmatrix} \sim \begin{bmatrix} 1 & 3 & 4 & b1 \ 0 & 14 & 10 & b2+4b1 \ 0 & 0 & 0 & b3+3b1 - \frac{1}{2}(b2+4b1) \ \end{bmatrix}$

  • The third entry in the augmented column is $b3+3b1 - \frac{1}{2}b2 - 2b1 = b1 - \frac{1}{2}b2 + b3$.

  • The system $Ax=b$ is not consistent for every $b$ because some choices of $b$ can make $(b1 - \frac{1}{2}b2 + b3)$ nonzero, leading to an inconsistent system.

  • The reduced matrix shows that $Ax = b$ is consistent if and only if the entries in $b$ satisfy:
    $b1 - \frac{1}{2}b2 + b3 = 0$

  • This equation describes a plane through the origin in $R^3$, which is the set of all linear combinations of the columns of $A$. The equation fails to be consistent for all $b$ because the echelon form of $A$ has a row of zeros.

Theorem 4 (Page 3): Equivalence of Four Statements

• Let $A$ be an $m \times n$ matrix. The following statements are logically equivalent (all true or all false):

  • a. For each $b$ in $R^m$, the equation $Ax = b$ has a solution.

  • b. Each $b$ in $R^m$ is a linear combination of the columns of $A$.

  • c. The columns of $A$ span $R^m$. (This means $Span{v1, \dots, vp} = R^m$ if ${v1, \dots, vp}$ are the columns of $A$).

  • d. The matrix $A$ has a pivot position in every row.

• Warning (Page 4): Theorem 4 is about the coefficient matrix $A$, not the augmented matrix $[A \ b]$. If an augmented matrix $[A \ b]$ has a pivot position in every row, the equation $Ax = b$ may or may not be consistent (e.g., if the pivot is in the augmented column).

• Proof Sketch (Page 6):

  • Statements (a), (b), and (c) are equivalent by definition.

  • To show (a) and (d) are equivalent: Let $U$ be an echelon form of $A$.

    • If (d) is true (pivot in every row of $U$), then $[U \ d]$ cannot have a pivot in the augmented column, so $Ax = b$ has a solution for any $b$ (meaning (a) is true).

    • If (d) is false (last row of $U$ is all zeros), then we can construct a vector $d$ with a $1$ in its last entry. The system $[U \ d]$ represents an inconsistent system. Since row operations are reversible, this implies an original system $[A \ b]$ that is also inconsistent, thus (a) is false.

Computation of $Ax$: The Row-Vector Rule

• This rule provides a more efficient method for calculating entries in $Ax$ by hand.

• Example 4 (Page 4): Compute $Ax$, where $A = \begin{bmatrix} 2 & 3 & 4 \ -1 & 5 & -3 \ 6 & -2 & 8 \ \end{bmatrix}$ and $x = \begin{bmatrix} x1 \ x2 \ x3 \ \end{bmatrix}$.

  • By definition: $Ax = x1 \begin{bmatrix} 2 \ -1 \ 6 \ \end{bmatrix} + x2 \begin{bmatrix} 3 \ 5 \ -2 \ \end{bmatrix} + x3 \begin{bmatrix} 4 \ -3 \ 8 \ \end{bmatrix} = \begin{bmatrix} 2x1 + 3x2 + 4x3 \ -x1 + 5x2 - 3x3 \ 6x1 - 2x2 + 8x3 \ \end{bmatrix}$

  • Notice that the first entry in $Ax$ ($2x1 + 3x2 + 4x3$) is the sum of products of entries from the first row of $A$ and the entries in $x$.

  • Similarly, the second entry ($-x1 + 5x2 - 3x3$) is from the second row of $A$ and $x$. And so on.

• Row-Vector Rule for Computing $Ax$ (Page 4): If the product $Ax$ is defined, then the $i^{th}$ entry in $Ax$ is the sum of the products of corresponding entries from row $i$ of $A$ and from the vector $x$.

• Example 5 (Page 5):

  • a.
    $\begin{bmatrix} 2 & -3 \ 8 & 0 \ -5 & 2 \ \end{bmatrix} \begin{bmatrix} 4 \ 7 \ \end{bmatrix} = \begin{bmatrix} (2)(4) + (-3)(7) \ (8)(4) + (0)(7) \ (-5)(4) + (2)(7) \ \end{bmatrix} = \begin{bmatrix} 8 - 21 \ 32 + 0 \ -20 + 14 \ \end{bmatrix} = \begin{bmatrix} -13 \ 32 \ -6 \ \end{bmatrix}$

  • b. $\begin{bmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \ \end{bmatrix} \begin{bmatrix} r \ s \ t \ \end{bmatrix}$

    • This specific matrix is called an identity matrix and is denoted by $I$.

    • The calculation shows that $I \begin{bmatrix} r \ s \ t \ \end{bmatrix} = \begin{bmatrix} (1)(r) + (0)(s) + (0)(t) \ (0)(r) + (1)(s) + (0)(t) \ (0)(r) + (0)(s) + (1)(t) \ \end{bmatrix} = \begin{bmatrix} r \ s \ t \ \end{bmatrix}$, so $Ix = x$ for every $x$ in $R^3$.

    • There is an analogous $n \times n$ identity matrix, often written as $In$, for which $Ix = x$ for every $x$ in $R^n$.

Properties of the Matrix-Vector Product (Theorem 5)

• If $A$ is an $m \times n$ matrix, $u$ and $v$ are vectors in $R^n$, and $c$ is a scalar, then:

  • a. Distributive Property: $A(u + v) = Au + Av$

  • b. Scalar Multiplication Property: $A(cu) = c(Au)$

• Proof Sketch (Page 5, for $n = 3$):

  • Let $A = \begin{bmatrix} a1 & a2 & a3 \end{bmatrix}$, and let $ui$ and $vi$ be the $i^{th}$ entries of $u$ and $v$ respectively.

  • For (a):
    $A(u + v) = \begin{bmatrix} a1 & a2 & a3 \end{bmatrix} \begin{bmatrix} u1 + v1 \ u2 + v2 \ u3 + v3 \ \end{bmatrix}$
    $= (u1 + v1)a1 + (u2 + v2)a2 + (u3 + v3)a3$
    $= (u1a1 + u2a2 + u3a3) + (v1a1 + v2a2 + v3a3)$
    $= Au + Av$

  • For (b):
    $A(cu) = \begin{bmatrix} a1 & a2 & a3 \end{bmatrix} \begin{bmatrix} cu1 \ cu2 \ cu3 \ \end{bmatrix}$
    $= (cu1)a1 + (cu2)a2 + (cu3)a3$
    $= c(u1a1) + c(u2a2) + c(u3a3)$
    $= c(u1a1 + u2a2 + u3a3)$
    $= c(Au)$

Numerical Note on Computation of $Ax$ (Page 6)

• To optimize computer algorithms for $Ax$, the sequence of calculations should involve data stored in contiguous memory locations.

• Fortran: Stores matrices as sets of columns. Algorithms in Fortran compute $Ax$ as a linear combination of the columns of $A$ (consistent with the definition).

• C: Stores matrices by rows. Algorithms in C should compute $Ax$ using the row-vector rule (multiplication of rows of $A$ by vector $x$).

Practice Problems (Page 6)

• Examples of exercises include:

  • Exhibiting $b$ as a linear combination of columns of $A$ given that $x$ is a solution to $Ax=b$.

  • Verifying Theorem 5(a) for specific matrices and vectors.

  • Constructing matrices $A$ and vectors $b, c$ such that $Ax=b$ has a solution but $Ax=c$ does not.

  • Computing matrix-vector products using both the definition and the row-vector rule.

  • Converting between matrix equations and vector equations.