Linear Algebra Notes

Linear Systems of Equations

Fields

Fields are denoted by $F$ and examples include:

• Real numbers: $F = \mathbb{R}$
• Rational numbers: $F = \mathbb{Q}$
• Complex numbers: $F = \mathbb{C}$
• $F = \mathbb{Z}_{4,7}$

Linear System Definition

A linear system consists of $m$ equations in $n$ unknowns ($x1, x2, …, x_n$):

$a<em>{11}x1 + a</em>{12}x2 + … + a_{1n}xn = b1$

$a<em>{21}x1 + a</em>{22}x2 + … + a_{2n}xn = b2$

$\vdots$

$a<em>{m1}x1 + a</em>{m2}x2 + … + a<em>{mn}xn = b</em>m$

Where $a<em>{11}, a</em>{12}, …, a<em>{mn}, b1, …, b</em>m \in F$.

Matrix Notation

• Coefficient Matrix (A):

  $A = \begin{bmatrix} a<em>{11} & a</em>{12} &amp; … &amp; a<em>{1n} \ a</em>{21} &amp; a<em>{22} & … & a</em>{2n} \ \vdots &amp; \vdots &amp; \ddots &amp; \vdots \ a<em>{m1} & a</em>{m2} &amp; … &amp; a_{mn} \end{bmatrix}$

• Matrix of Unknowns (X):

  $X = \begin{bmatrix} x1 \ x2 \ \vdots \ x_n \end{bmatrix}$

• Right Hand Side Matrix (B):

  $B = \begin{bmatrix} b1 \ b2 \ \vdots \ b_m \end{bmatrix}$

• Augmented Matrix ([A|B]):

  $[A|B] = \begin{bmatrix} a<em>{11} & a</em>{12} &amp; … &amp; a<em>{1n} & b1 \ a</em>{21} &amp; a<em>{22} & … & a</em>{2n} &amp; b2 \ \vdots &amp; \vdots &amp; \ddots &amp; \vdots &amp; \vdots \ a<em>{m1} & a</em>{m2} &amp; … &amp; a_{mn} &amp; bm \end{bmatrix}$

Solution to a Linear System

An $n$-tuple of numbers $s1, s2, …, sn \in F$ is a solution to the system $[A|B]$ if, upon substituting $x1 = s1, x2 = s2, …, xn = s_n$, every equation of the system becomes a correct equality.

Solution Set

The solution set of the system $[A|B]$ is the set of all solutions to $[A|B]$. Solving the system means finding its solution set.

Consistent and Inconsistent Systems

• Consistent System: A system with at least one solution.
• Inconsistent System: A system with an empty solution set.

Example

• System 1

  $x1 + x2 = 5$

  $x1 + 2x2 = 6$

  Augmented matrix:

  $\begin{bmatrix} 1 &amp; 1 &amp; 5 \ 1 &amp; 2 &amp; 6 \end{bmatrix}$

  Applying $R2 + (-1)R1 \rightarrow R_2$:

  $\begin{bmatrix} 1 &amp; 1 &amp; 5 \ 0 &amp; 1 &amp; 1 \end{bmatrix}$

  Applying $R1 + (-1)R2 \rightarrow R_1$:

  $\begin{bmatrix} 1 &amp; 0 &amp; 4 \ 0 &amp; 1 &amp; 1 \end{bmatrix}$

  The only solution is $x1 = 4, x2 = 1$. Solution set: ${[4, 1]}$

• System 2

  $x1 + x2 = 5$

  $2x1 + 2x2 = 9$

  Augmented matrix:

  $\begin{bmatrix} 1 &amp; 1 &amp; 5 \ 2 &amp; 2 &amp; 9 \end{bmatrix}$

  Applying $R2 + (-2)R1 \rightarrow R_2$:

  $\begin{bmatrix} 1 &amp; 1 &amp; 5 \ 0 &amp; 0 &amp; -1 \end{bmatrix}$

  This indicates no solution exists. The solution set is empty, ${}$, and the system is inconsistent.

• System 3

  $x1 + x2 = 5$

  $2x1 + 2x2 = 10$

  Augmented matrix:

  $\begin{bmatrix} 1 &amp; 1 &amp; 5 \ 2 &amp; 2 &amp; 10 \end{bmatrix}$

  Applying $R2 + (-2)R1 \rightarrow R_2$:

  $\begin{bmatrix} 1 &amp; 1 &amp; 5 \ 0 &amp; 0 &amp; 0 \end{bmatrix}$

  $x1 + x2 = 5$, so $x1 = 5 - x2$. There are infinitely many solutions. Any solution is in the form ${[5-t, t] | t \in F}$.

Equivalent Linear Systems

Two linear systems in $n$ unknowns are equivalent if they have the same solution set.

Elementary Row Operations

1. Interchanging two rows.
2. Multiplying a row by a nonzero number.
3. Replacing a row by the sum of itself and a multiple of another row.

Theorem: Elementary row operations do not change the solution set.

Questions to Think About

• Will multiplying a row by 0 change the solution set?
• Will replacing a row by a sum of itself and a multiple of itself change the solution set?

Definitions

• Nonzero Row: A row with at least one nonzero entry.
• Zero Row: A row consisting of all zeros.
• Leading Entry: The leftmost nonzero entry in a nonzero row.

Row Echelon Form (REF)

A matrix is in REF if:

1. All nonzero rows are above any zero rows.
2. Each leading entry of a nonzero row is in a column strictly to the right of the leading entry of the row above it.

Reduced Row Echelon Form (RREF)

A matrix is in RREF if:

1. It is in REF.
2. The leading entry in each nonzero row is 1.
3. The leading entry is the only nonzero entry in its column.

Pivot Position and Column

• Pivot Position: A location in a matrix $A$ that corresponds to a leading 1 in RREF(A).
• Pivot Column: A column of $A$ that contains a pivot position.

Theorems and Observations

• Any matrix can be reduced to RREF by a sequence of elementary row operations.
• The RREF of a matrix is unique.

Finding Solution Sets in RREF

• Observation 1

  If B is a pivot column, then there is a '1' in the form $\begin{bmatrix} 0 \ … \ 0 \ 1 \end{bmatrix}$. The system is inconsistent.

• Observation 2

  Assume $B$ is not a pivot column.

  • Lead Variables: Variables corresponding to pivot columns.
  • Free Variables: All other variables.

  To find the solution set, solve for lead variables in terms of free variables.

Example

$x1 + 6x2 + 3x4 = 0$

$x3 + 4x4 = 5$

$x5 = 7$

$x1, x3, x5$ are lead variables.

$x2, x_4$ are free variables.

$x1 = -6x2 - 3x4$

$x3 = 5 - 4x4$

$x5 = 7$

Solution set:

${\begin{bmatrix} -6t - 3s \ t \ 5 - 4s \ s \ 7 \end{bmatrix} | s, t \in F}$

Conclusion

A linear system is consistent if and only if $B$ is not a pivot column.

If the system is consistent:

• It has a unique solution when all variables are lead (no free variables).
• It has many solutions when there are free variables.

Example: Solving a System

$x1 + x2 + x3 + x4 + x5 = 1$

$-x1 - x2 + x5 = -1$

$-2x1 - 2x2 + 3x5 = 1$

$x3 + x4 + 3x5 = 3$

$x1 + x2 + 2x3 + 2x4 + 4x_5 = 4$

Applying elementary row operations leads to:

Solution set:

${\begin{bmatrix} 4 - t \ t \ -6 + s \ s \ 3 \end{bmatrix} | s, t \in F}$

$x1, x3, x5$ are lead variables.

$x2, x_4$ are free variables.

$M_{m \times n}(F)$

Vector Spaces

Examples of Vector Spaces

1. Ordered Pairs of Real Numbers with Component-wise Operations

   $\mathbb{R}^2 = { \begin{bmatrix} a1 \ a2 \end{bmatrix} | a1, a2 \in \mathbb{R} }$

   $\begin{bmatrix} a1 \ a2 \end{bmatrix} + \begin{bmatrix} b1 \ b2 \end{bmatrix} = \begin{bmatrix} a1 + b1 \ a2 + b2 \end{bmatrix}$

   $c \begin{bmatrix} a1 \ a2 \end{bmatrix} = \begin{bmatrix} ca1 \ ca2 \end{bmatrix}$

   Geometrically, vectors in the plane are directional vectors represented by directed line segments from (0,0) to $(a1, a2)$.

   Scalar multiplication changes the length and direction (or preserves direction if c > 0 and reverses direction if c < 0).

   Vector addition is done by the parallelogram rule.

2. Ordered n-tuples of Real Numbers with Component-wise Operations

   $\mathbb{R}^n = { \begin{bmatrix} a1 \ \vdots \ an \end{bmatrix} | a_i \in \mathbb{R} }$

   $\begin{bmatrix} a1 \ \vdots \ an \end{bmatrix} + \begin{bmatrix} b1 \ \vdots \ bn \end{bmatrix} = \begin{bmatrix} a1 + b1 \ \vdots \ an + bn \end{bmatrix}$

   $c \begin{bmatrix} a1 \ \vdots \ an \end{bmatrix} = \begin{bmatrix} ca1 \ \vdots \ can \end{bmatrix}$

   Two n-tuples are equal if $ai = bi$ for all $i$.

3. Ordered n-tuples of Elements of a Field F with Component-wise Operations

   $F^n = { \begin{bmatrix} a1 \ \vdots \ an \end{bmatrix} | a_i \in F }$

   $\begin{bmatrix} a1 \ \vdots \ an \end{bmatrix} + \begin{bmatrix} b1 \ \vdots \ bn \end{bmatrix} = \begin{bmatrix} a1 + b1 \ \vdots \ an + bn \end{bmatrix}$

   $c \begin{bmatrix} a1 \ \vdots \ an \end{bmatrix} = \begin{bmatrix} ca1 \ \vdots \ can \end{bmatrix}$

4. m x n Matrices with Entries from Field F and Component-wise Operations

   $M<em>{m \times n}(F) = { \begin{bmatrix} a</em>{11} &amp; … &amp; a<em>{1n} \ \vdots & \ddots & \vdots \ a</em>{m1} &amp; … &amp; a<em>{mn} \end{bmatrix} | a</em>{ij} \in F }$

   Matrix addition and scalar multiplication are defined component-wise.

5. Polynomials with Coefficients from Field F

   A polynomial of degree n is an expression of the form:

   $anx^n + a_{n-1}x^{n-1} + … + a1x + a0$

   where $ai \in F$ for all $i$ and $an \neq 0$.

   The polynomial 0 (where $a_i = 0$ for all $i$) has degree -1.

   Two polynomials are equal if their corresponding coefficients are equal (i.e., $ai = bi$ for all $i$).

   Polynomial addition is defined by collecting like terms:

   $(anx^n + … + a1x + a0) + (bnx^n + … + b1x + b0) = (an + bn)x^n + … + (a1 + b1)x + (a0 + b0)$

   Scalar multiplication is defined as:

   $c(anx^n + … + a1x + a0) = (can)x^n + … + (ca1)x + (ca0)$

   Examples of Polynomial Vector Spaces

   • $Pn(F) = { anx^n + a_{n-1}x^{n-1} + … + a1x + a0 | ai \in F }$: polynomials of degree $\leq n$
   • $P(F) = { anx^n + a<em>{n-1}x^{n-1} + … + a1x + a0 | a</em>i \in F, n \geq 0 }$: polynomials of any degree

6. Functions from a Set S to a Field F with Pointwise Operations

   Let $S$ be a set and $F$ be a field. Then $f: S \rightarrow F$ means $f$ is a function from $S$ to $F$.

   $F(S, F) = {f | f: S \rightarrow F}$

   Two functions $f, g: S \rightarrow F$ are equal if $f(x) = g(x)$ for all $x \in S$.

   Addition and scalar multiplication are defined point-wise:

   $(f + g)(x) = f(x) + g(x)$

   $(cf)(x) = c f(x)$

Justifying Gaussian Elimination

Consider W a mxn matrix. Elementary operations are reversible.

Let $W'$ is obtained from $W$ by one elementary now operation.

Proposition 1: $W$ can be obtained from $W'$ by one elementary now operation.

Proof:

Case 1:

Assume that $W'$ is obtained from $W$ by interchanging two rows $Ri \leftrightarrow Rj$;

$W \xrightarrow{Ri \leftrightarrow Rj} W' \xrightarrow{Ri \leftrightarrow Rj} W$

Case 2:

Assume that $W'$ is obtained from $W$ by multiplying a row by non-zero scalar $c Ri \rightarrow Ri$;

$W \xrightarrow{c Ri \rightarrow Ri} W' \xrightarrow{\frac{1}{c} Ri \rightarrow Ri} W$

Case 3:

Assume that $W'$ is obtained from $W$ by replacing a row by the sum of itself and a multiple of another row $Ri + c Rj \rightarrow R_i$;

$W \xrightarrow{Ri + c Rj \rightarrow Ri} W' \xrightarrow{Ri + (-c) Rj \rightarrow Ri} W$

Corollary: If $W'$ is obtained from $W$ by a finite sequence of row operations, then $W$ can be obtained from $W'$ by a finite sequence of row operations.

Proposition 2

Let $[A|B]$ be a linear system of $m$ equations in $n$ variables: $AX=B$.

Let $S=\begin{bmatrix} s1 \ s2 \ … \ s_n \end{bmatrix}$ be a solution to the system $[A|B]$.

Assume that $[A'|B']$ is obtained from $[A|B]$ by one elementary row operation. Then $S$ is a solution to $[A'|B']$.

Proof:

We have that

$a<em>{k1}S1 + a</em>{k2}S2+ … +a<em>{kn}Sn=b</em>k\quad for\space all\space k=\overline{1,m}$

Case 3:

Assume $[A'|B']$ is obtained from $[A|B]$ by replacing a row sum by a multiple of another row, $Ri \rightarrow Ri+cRj$

For equation of $[A'|B']$, we get

(a{i1}+ca{j1})S1+(a{i2}+ca{j2})S2+…+(a{in}+ca{jn})Sn=
=(a{i1}S1+a{i2}S2+…+a{in}Sn)+c(a{j1}S1+a{j2}S2+…+a{jn}Sn)=
=bi+cbj

Hance S satisfies equality of $[A'|B']$

Consequences:

If $[A'|B']$ is obtained from $[A|B]$ by one elementary row operation, then

$S$ is a solution to $[A|B]$ if and only if

$S$ is a solution to $[A'|B']$.

If $[A'|B']$ is obtained from $[A|B]$ by a finite sequence of row operations, then the solution set of $[A'|B']$ is equal to/same as the solution set of $[A|B]]$.

Proving that RREF can be obtained from any matrix by elementary operations::

Lemma 3 : Let $W$ be an mxn matrix. Then there exists $W'$ RREF such that $W'$ obtained from $W$ by elementary operations. Also, given column equal to $0$ implies columns in $W'$ is $0$.

Proof: With indication in number of nonzero rows in $W$.

1. If $W$ is an zero matrix, then is already is RREF

2. if $W$ not a zero matrix, there exits $l \leq k \leq h$, $W<em>{ik}\neq0$ choose $k$ to be with $W</em>{ik}\neq0$, and all coefficients left of column $k$ is zero(0):

   Then operations cRi+ Ri- \rightarrow> Ri, $W<em>{ik}\neq0$. We call $W</em>{ik}=1$ via $\frac {1}{W<em>{ik}}.$Then $R1 \leftrightarrow Ri => W</em>{jk}=0$ for all $2 \leq i \leq m$.

   Consider matrix $V$, then $(m-1)xn$ matrix obtain from $W'$ by deleting the first row. With indicate hypothesis exits matrix $V'$ in RREF. Putting row 1 $W'$ of matrix $W3$ as row 1 of matrix $V'$ the entries $W_{3k} =1$ for all. Entries in leading columns of $v'$ are zero 1.

Vector Spaces(section 1.2)

Set $V$ with two operations is a vector space if the 8 axioms:

Axiom1: $\forall$ $X1$, $X2**$\in V, X1+X2=X2+X1
Axiom2: \forall$$X1$,$X2$,$\X3** $\in V, (X1+X2)+X3=X1+(X2+X3)$
Axiom3: $\exists u\in V sit \forall X\in V, u+X=X$
Axiom4: $\forall X\in V, \exists y \in V, X+y=u$ $u$ comes from Axiom3
Axiom5: $\forall X\in V,</p><p>Axiom1:$\forall$$X1$,$X2$$\in V, X1+X2=X2+X1

Axiom2: \forall$$X1$,$X2$,$
X3$$\in V, (X1+X2)+X3=X1+(X2+X3)

Axiom3: \exists u\in V sit \forall X\in V, u+X=X

Axiom4: \forall X\in V, \exists y \in V, X+y=u$$u comes from Axiom3

Axiom5: \forall X\in V, 1X=X

Axiom6: \forall a,b \in F, X \in V, (ab)X=a(bX)

Axiom7: \forall a \in F, X,Y \in V, a(X+Y)=aX+aY

Axiom8: \forall a,b \in F, X \in V, (a+b)X=aX+bX$$