Merced College; Don Power

LINEAR ALGEBRA - CHAPTER 1, LECTURE

1.1 Introduction to Systems of Linear Equations Hwk 1adf, 2, 3ac, 4ac, 5b, 6, 7, 8, 12, T1 (0n page 79).
For T1, I suggest the 10-minute tour of Maple-10, as well as the introductory section on Maple in the web site.

Def: Linear equation: Form a₁x₁ + a₂x₂ + ... + a_nx_n = b

Note subscripts

Task: Is an equation linear or not?

Constants: a₁, a₂, ... , a_n, b

Unknowns: x₁, x₂, ..., x_n

Solution: a sequence of n numbers s₁, s₂, ..., s_n satisfying the equation is when we sub x₁=s₁ etc

General solution (solution set) is the set of all solutions.

Task: Find a parameterized solution set for a single linear equation, as in Ex 3

Linear system [sysem of linear equations]: a finite set of linear equations in x₁, x₂, ..., x_n

Solution: a sequence of n numbers s₁, s₂, ..., s_n satisfying every equation in the system.

Not all systems have solutions:

Inconsistent -- No solutions exist

Consistent -- At least one solution exists

Nature of solutions for linear systems: We have either

[demonstrate geometrically]

No solutions, or

Exactly one solution, or

Infinitely many solutions

Augmented Matrix: coefficients of a system such as:

Ex: [Sol (2, -1, 4)], in general (what is bottom row?)

Double subscripting to denote rows and columns: in general and in a specific matrix

We'll need to be familiar with general form to state and prove theorems.

Elementary Row Operations - valid for equations or for matrices

1. Interchange any two rows

2. Multiply a row by a constant

3. Add a multiple of a row to any other row.

Illustrate on the system above (full descrip of Gauss-Jordan elimination in next lesson)

Gaussian elimination to row echelon form (follow with back-substitution)

Result not unique -- rearranging equations to start with gives different results

Gauss-Jordan elimination to reduced row echelon form

Result is unique.

1.2 Gaussian Elimination Hwk: 1acegi, 2ade, 3acd, 4abcd, 5b, 6a, 8b, 9c, 10c, 12, 13b, 16a, 17, 18, 20, 22, 24, 25, 32, T1
#24: Let 1/x = u etc. #25: for each point, substitute x and y into the given form. Maple sample: with(linalg); a:=matrix( [[2,1,3],[1,-5,4]] ), rref(a);

Criteria for row echelon form ("ref" in a graphing calculator)

First entry in each row is 1 (called "leading 1")

The leading 1 in any row is to the right of the leading 1 in the previous rows

All-zero rows are at the bottom of the matrix

Additional criterion for reduced row echelon form ("rref" in a graphing calculator or Maple)

All entries above and below an initial 1 are 0.

Ex 1-2 show samples of matrices in ref and rref

Ex 3: Given the rref of a matrix, write the solution

Translate directly to equations -- In the case of a unique solution, you are done.m If not, …

Solve for each leading variable

The remaining variables are "free variables"

Replace each free variable with a "parameter" (arbitrary value assigned to a free variable)

Ex Like 3: Solve

Sol: free variables are x₂ and x₄. Let x₂ = s, x₄ = t. Then solution is:

Step-by-step process for Gauss-Jordan elimination (per text)

1. Locate the leftmost column that has a nonzero element

2. Row-swap to move [smallest, in absolute value] nonzero entry "a" to the top of the column

3. Multiply the first (top) row by 1/a to introduce a leading 1

[This can introduce fractions: See note below for alternatives]

4. Add suitable multiples of the top row to the other rows to make all entries below the "leading 1" 0

[Let "b" be the entry in the lower row: add "-b" times the top row to the lower row]

[For Gauss-Jordan elimination, do the same to entries above the leading 1]

5. Cover the top row and begin again with step 1 on the resulting submatrix

6. [if you have not already cleared entries above the leading 1s]:

Beginning with the last nonzero row, work upward to introduce zeros above leading 1s.

Note: Alternatives exist at step 3 to avoid fractions, including

Linear combinations of rows (you can get a 1 if any two entries that are relatively prime)

Multiplying other rows by "a," and postponing division by a until the rref is otherwise complete

Ex 5 and 7 -- example of Gauss-Jordan elimination with infinite (parameterized) solution

We did one in Ex 1

Ex 6 -- example of Gaussian elimination, with back-substitution

Thm: A linear system with more than one solution has infinitely many solutions

Proof: Gauss-Jordan elimination can result in either

No solutions (if any row results in 0 = non-zero constant),

One unique solution, in which there are no free variables, or

A solution for which one or more variables (corresponding to leading 1s) are solved in terms of free variables. Since a free variable can take on infinite values, infinitely many solutions are possible

Def: Homogeneous linear system -- System of linear equations for which the constants are all 0.

Thm: A homogeneous system always has at least one solution (called the "trivial solution"),
x₁ = x₂ = ...=x_n = 0

Proof: Let x₁ = x₂ = ...=x_n = 0.

The left side of every equation becomes 0; every equation is 0=0; every equation is true

Ex: Consider any two lines y=mx+b, with b=0: y=m₁x, y=m₂x; intersect at the origin

Note that if they intersect anywhere else, they must be the same line: infinite solutions

Thm 1.2.1: A homogeneous system with more unknowns than equations has infinitely many solutions

Proof: Suppose we have m equations in n unknowns, with m<n.

Gauss-Jordan elimination can reduce the number of non-zero rows (equations) to some r £ m< n.

Since there will be only r leading 1's, there are n-r free variables, with n-r>1

A free variable can take on an infinite number of values, so there are infinitely many solutions.

Computer solutions

Be able to set up and perform rref to get solution of systems of linear equations with

Graphing calculator

Computer:

Special Techniques:

#24: Let 1/x = u etc. #25-6: for each point, substitute x and y into the given form

r₁

r₂

:

r_m

1.3 Matrices and Matrix Operations Hwk 1beg, 2, 3ej, 4dh, 5gi, 6a, 7b, 8a, 9a, 13a, 14a, 15a, 20, 21abd, 25, 31ab, T4. For 31a, argue from the dimensions of A and A^T; for 31b, start by partitioning A into


row matrices, so A = . So A^T = …?, Multiply these to get AA^T , etc.

Matrix - Def

Double subscript notation for general matrix and its entries

Compact notation for a matrix: A = [a_ij]_mxn or just [a_ij]

Compact notation for an entry: a_ij = (A)_ij

Square matrices have a main diagonal

Row matrices and column matrices are also referred to as vectors

Double subscripting is unnecessary

Notation: use boldface (in print) or arrow over letter (handwritten)

We will need to talk about the row and column matrices that make up a complete matrix.

r₁

r₂

r₃

Text uses notation r and c, but that doesn't specify which matrix the row and column are from:

c1

c2

c3

c4

A = = for a 3X4 matrix. A has been partitioned into submatrices

To avoid ambiguity with several matrices write A_r1, A_c2, etc. Text includes general discussion of partitioning

Operations: [note #1-5 the definitions imply that A and B have the same dimensions]

1. Equality Component-wise A = B ==> a_ij = b_ij for every i,j

2-3. Addition/subtraction " (A+B)ij = a_ij + b_ij for every i,j … etc.

4. Scalar mult " How would you write this?

5. Linear combination " How would you write this?

6. Dot product of two vectors of the same length (we'll do as a row vector r dotted with a column vector c):
r dot c = r₁c₁ + r₂c₂ + ... + r_nc_n

7. Matrix mult: Each entry is calculated by (AB)ij = (A)_ri dot (B)_cj

Resulting matrix will have dimension : A_mxr x B_rxn = (AB)_mxn

Example…

Task for mult: Given dimensions of A and B, determine whether the product is defined, and the dimension of the result.

Matrix Multiplication

A_mxrB_rxn=C_mxn where cij = A_riB_cj = a_i1b_1j + a_i2b_2j + ... + a_irb_rj = (A)_ri dot (B)_cj

As in problem 15, partitioned matrices can be multiplied by block multiplication

Partition into rows and columns, thus:

Ar1Bc1	Ar1Bc2	...	Ar1Bcn
Ar2Bc1	Ar2Bc2	...	Ar2Bcn
:	:		:
ArmBc1	ArmBc2	...	ArmBcn

AB = =

This gives detail for each entry.

The matrix as a whole can be written either as

AB = A [B_c1 B_c2 ... B_cn ] = [ AB_c1 AB_c2 ... AB_cn ] Example 7a in textbook

or as

A_r1

A_r2

:

A_r4

A_r1B

A_r2B

:

A_rmB

AB = B = Example 7b in textbook

To select a particular column, say column 2:

from [AB] = ... select only the part of B that refers to column 2

[AB]_c2 = AB_c2 Formula 6 in textbook

Expand this result, rewriting A in terms of columns and showing all the entries of B_c2:

[AB]_c2=

= b₁₂ A_c1 + b₂₂ A_c2 + ... + b₂₂ A_cr Formula 10 and Examples 8a & 9 in textbook

To select a particular row, say row 2:

from [AB] = ... select only the part of A that refers to row 2

[AB]_r2 = A_r2B Formula 7 in textbook

Expand this result, showing all the entries of A_r2 and rewriting B in terms of rows:

= a₂₁B_r1 + a₂₂B_r2 + ... + a_2rB_rr Example 8b in textbook

Biggie: We can represent a linear system as the result of a matrix mult. AX = B, with the solution as X=A^-1B

Transpose: Interchange rows and columns: A^T is defined by A^T = B è aij = bji and A_mxn è B_nxm

Trace of a square matrix is the sum of the entries on the main diagonal: tr(A) = a₁₁ + a₂₂ + … + a_nn

1.4 Inverses; Rules for Matrix Arithmetic Hwk part b for 1-7; 9b, 14, 15a, 17, 21, 23 graphing calculator , 29ab, 34

Hints for #14: 4B factors into 4I times B (Why?); if B has an inverse, then BB^-1=I;

Hint for 23: Look for a function that applies an exponent of –1; on the TI-89, type in the exponent.

Properties of Matrices

See the properties in Thm 1 and 2. They should all make sense. What is surprising are properties that do not hold true for matrices:

1. Multiplication is not commutative. See Ex1 for a counterexample

2. The cancellation law (for multiplication) does not hold. That is, If AB = AC (with A not the zero matrix), it does not necessarily mean that B = C. Counterexample in Ex 3

3. Zero factorization does not hold. That is, AB = 0 does not imply that A=0 or B=0.

(Counterexample in Ex 3, but exercise 17 shows a case where the property does hold.)

Proof technique: If you want to prove that something is not true in general, show one counterexample.

Identity Matrices

I is an identity matrix if IA = A or AI = A

Different dimensions could be called for here. What dimensions are needed for I to get IA_mxn = A_mxn or A_mxnI = A_mxn?

Observation: Every identity matrix is a square matrix with 1s on the main diagonal, 0s elsewhere.

Thm 3: Applies to square matrices: If R = rref(A_nxn), then either A has a row of 0s or A = I_n

Proof: from the def of rref, each leading 1 is to the right of the previous one; with n, rows, if every row has a leading 1, we get 1s on the main diagonal and 0s elsewhere; if we have fewer than n leading 1s, we get a row of 0s.

Inverse of a Matrix

Def: B is an inverse of A if AB = BA = I. Observations:

1. This implies A and B must be square matrices of the same size. Why? (reason from dimensions)

2. Not all square matrices have inverses. Counterexample: Ex 6, where A has a column of 0s (note the mult used to get just col 3 of BA, which should be I)
We will need a better test: [[1 2][2 4]] is also singular, but the test used here doesn't show it.

3. Def: A square matrix that has no inverse is singular.

4. The inverse of a matrix A is called A^–1. So we can write A A^–1=1 and A^–1A=1

5. Statement 4 makes no sense unless the inverse is unique. Thm 4 below

6. To prove that a given matrix B is the inverse of A, you must show both AB = I and BA = I

Uniqueness of an inverse

Thm 4: If an inverse exists, it is unique. The text statement of the thm is really an outline of the proof: Assume B and C are both inverses of the same matrix A, and show that B must equal C.

[Note on proofs: this is a standard technique for showing uniqueness]

Here is one way to write the proof – slightly different from text (Where does this use the assumptions?):

B = BI = B(AC) = (BA)C = IC = C

Thm 5: A formula for the inverse of a 2x2 matrix.

Text's proof: AB = BA = I

"Constructive proof" derive the formula by multiplying A by B = [[e f][g h]], set result = I, equate corresponding elements, solve for e,f,g,h

Inverse of a product

Thm 6: Let A and B be invertible matrices of the same dimension. Then AB is invertible, and (AB)^–1 = B^–1A^–1

Proof: The trick is to work with AB rather than (AB)^–1. We show that B^–1A^–1 is the inverse of AB by writing (B^–1A^–1)(AB) and (AB)(B^–1A^–1). [so the other trick is to arrange these so that A is next to A^–1, and B is next to B^–1]. Both expressions simplify to I (your proof should show the full detail, as in the text), so AB is invertible, and the inverse is B^–1A^{–1 Then} we apply the inverse notation to complete the proof.

Powers and Exponents

See the def of A⁰, Aⁿ, A^–n

Thm 7 and 8 show that ordinary laws of exponents hold

A^rA^s = ..., (A^r)^s = ..., (A^–1)^–1 = ..., (Aⁿ)^–1 = (A^–1)ⁿ

One other property was surprising to me: (kA)^–1 = (1/k)A^–1

But this makes sense if we realize that the multiplicative inverse of a scalar is its reciprocal.

Polynomials: Observation: The variable x in the polynomial p(x) = a₀ + a₁x + ...+a_nxⁿ can be replaced by a square matrix A, as long as we replace the constant a₀ by an appropriate matrix, i.e. a_oI.

Ex. 9 in text

Thm 9: Properties of the transpose (recall, the transpose interchanges rows and columns)

a. The transpose of the transpose is the original matrix

b. The transpose of a sum is the sum of the transposes (we can distribute the ^T in (A ± B)^T)

c. We can factor out a scalar: (kA)^T = k(A^T)

d. (AB)^T = B^TA^T The transpose of a product is the product of the transposes, in the reverse order. Be able to prove.

Proof: First, verify that the matrix dimensions work, for any two matrices that can be multiplied.

Left side: (A_mxnB_nxp)^T = ((AB) _mxp)^T = (AB)_pxm

Right side: (B_nxp)^T (A_mxn)^T = B_pxnA_nxm = (AB)_pxm Same result, so the dimensions are correct.

Then verify that the entries in each cell are the same, that is (AB)^T_ij = (B^TA^T)_ij

This is easiest if we use the dot product: u dot v = u₁v₁ + u₂v₂ + ... + u_nv_n:

Left side: (AB)^T_ij = (AB)_ji = A_rj dot B_ci

Right side: (B^TA^T)_ij = B^T_ri dot A^T_cj = B_ci dot A_rj = A_rj dot B_ci (because the dot product is commutative); results are the same, so the two expressions equal each other.

Inverse if a transpose

Thm 10 For any invertible matrix A, A^T is also invertible, and (A^T)^–1 = (A^–1)^T The inverse of a transpose is the transpose of the inverse

Proof:

A is invertible, so AA^–1 = I and A^–1A = I

For each identity, take the transpose of both sides and simplify, so (AA^–1)^T = I^T =I and (A^–1A)^T = I^T =I

For each of these, clear the parentheses with Thm 9d: (A^–1)^TA^T = I and A^T(A^–1)^T=I

Apply the definition of an inverse, and we have that A^T is invertible, and the inverse is (A^–1)^T

Trace: tr(A) = sum of the elements on the main diagonal. Defined only for square matrices.

Example: tr(I) = dimension of I, since the main diagonal consists of 1's in every row.

1.5 Elementary Matrices and a Method for Finding A^-1 Hwk 1, 2, 3b, 5b, 6b, 7a, 8b, 10, 18, 21, 23

Concept (review from lesson 1.2 of selecting a row of a product): When multiplying two matrices EB, a specific row of the product is found by multiplying that same row of E times the matrix B, and the result in that row is a linear combination of the rows of B, with the coefficients coming from the entries in the same row of A.

Example, to find row 3 of EB, (EB)_r3 = E_r3B. Suppose row 3 of E is [2, –4, 3, 7]. Then row 3 of the product EB is 3B_r1 –4B_r2 +3B_r3 +7B_r4.

Elementary Matrices:

Elementary row operations can be done by multiplying on the left by an identity matrix that is slightly modified, as follows: [for this example, let E be the matrix on the left, and let it be dimension 5]:

1. Swapping rows 2 and 5: Both row 2 and row 5 change.

a. Row 2 of result requires the linear combination 0B_r1 + 0B_r2 + 0B_r3 + 0B_r4 + 1B_r5

so row 2 of E is [0 0 0 0 1], and

b. Row 5 of result requires the linear combination 0B_r1 + 1B_r2 + 0B_r3 + 0B_r4 + 1B_r5

so row 5 of E is [0 1 0 0 0]

c. The rest of the rows are the same as the identity matrix

2. Multiplying row 4 by the constant 7: Only row 4 changes.

a. Row 4 of result requires the linear combination 0B_r1 + 0B_r2 + 0B_r3 + 7B_r4 + 0B_r5

so row 4 of E is [0 0 0 7 0]

b. The rest of the rows are the same as the identity matrix

3. Multiply row 4 by the constant 7 and add the result to row 1: Only row 1 changes

a. Row 1 of result requires the linear combination 1B_r1 + 0B_r2 + 0B_r3 + 7B_r4 + 0B_r5

so row 4 of E is [1 0 0 7 0]

b. The rest of the rows are the same as the identity matrix

Inverses will reverse the effects. So to get the the inverse of

1. Swapping R1 and R5: repeat the swap

2. Multiplying R4 by 7: multiply R4 by 1/7

3. Multiplying R4 by 7 and adding result to R1: Multiply R4 by -7 and add result to R1

So row operations correspond to multiplying on the left by elementary matrices (Thm 1), and elementary matrices are invertible (Thm 2)

Since identity matrices can be produced from invertible matrices by a finite number of row operations, we have E₁E₂...E_nA = I. Consequences: The following are equivalent (Thm3):

1. A is invertible

2. Ax = 0 has only the trivial solution (from A^–1Ax = A^–10 = 0 ==> x = 0)

3. rref (A) = I (if x = 0, every variable = 0, which corresponds to I x= 0;

In Gauss Jordan elimination, this can only result from rref (A) = I

4. A can be expressed as a product of elementary matrices.

Proof: Since rref (A) = I, we have E₁E₂...E_nA = I. Thus A^–1 can be expressed as a product of elementary matrices. Solving, we get A = E_n^–1...E^–2E^–1, so A can be expressed as a product of elementary matrices

1.6 Further Results on Systems of Equations and Invertibility Hwk 2, 5, 11, 14, 17, 20, 25, 30, 31, T1

Thm 1: We can now prove that every linear system of equations has no solutions, exactly one solution, or infinitely many solutions.

Proof: we have all seen examples of systems with no solutions and examples with exactly one solution. [It takes only one example to show that the case can exist]. It remains to be shown that if more than one solution exists, then an infinite number of solutions exist. See text

Thm 2: If Ax = b, and A is invertible, there is a unique solution x = A^-1b. Proof: multiply on left by A^–1

Thm 3: We don't need to show both BA = I and AB = I to prove B = A^–1; either one is sufficient.

Proof: Mult first eqn on the right by A^–1, and mult second eqn on left by A^–1

Thm 4: Adds two more equivalent statements to the "big theorem," statements that are equivalent to "A is invertible:"

f. If Ax = b, there is a unique solution x = A^-1b This was thm 2 above.

e. Ax = b is consistent for every nx1 matrix b. Proof: follows from part f by def of "consistent"

e ==> a Solve Ax_i = b_i where the b_i's are all the columns of the identity matrix. Then the matrix whose columns are the solutions (the x_i's) is the inverse, for we will have A[x₁ x₂ ... x_n] = [b₁ b₂ ... b_n] = I

Thm 5: If a product is invertible, then so are the factors (provided they are square matrices of the same dimension). This is the converse if Thm 1.4.6

The homework asks you to state the contrapositive (if the then statement is false, then the if statement is false)

Fundamental Problem: Let A be an mxn matrix. Find all mx1 matrices b so that the system Ax = b is consistent.

1. We are interested in the case where A is not invertible, and may even not be square. From thm 4, we know that since A is not invertible, there cannot be a unique solution. So if any solution exists, there must be infinite solutions (by thm 1). We label the entries of b as b₁, b₂, ... , b_m, and find the rref of the augmented matrix. Observe what happens on the row(s) for which rref(A) is all-zero. This defines the conditions under which the system will be consistent.

2. In the case where A is invertible (so we know we will get a unique solution), rref(A) = I, so the final row of will not be all-zero. What we get, as in example 6, is a formula for each variable in terms of b₁, b₂, ... , b_m that is valid for every mx1 matrix b.

3. Calculator issue: most calculators do not handle the symbolic values, as needed in example 3. You can, however, get equivalent results by using separate columns for b₁, b₂, ... , b_m. (so that it looks like you are augmenting A with the identity matrix). Find rref of the augmented matrix, and read the coefficients of b₁, b₂, ... , b_m out of the rows for which rref(A) is all-zero. So for example 5, instead of entering the matrix as

1	1	2	b1
1	0	3	b2
2	1	3	b3

enter it as

1	1	2	1	0	0
1	0	3	0	1	0
2	1	3	0	0	1

(The first line would be interpreted as 1x₁ + 1x₂ + 2x₃ = 1b₁ + 0b₂ + 0b₃, etc.)

The rref of this matrix gives you a last line of [0 0 0 1 1 –1], representing 0 = b₁ + b₂ –b₃,
which is equivalent to the result you get by working the 3x4 matrix by hand.

1.7 Diagonal, Triangular, and Symmetric Matrices
Hwk 1, 2, 3, 4, 5, 6, 7, 8, 10b, 11a, 12 (calculators OK from now on), 15 (Note A² = A^TA for symmetric matrices, 22a (you will need Thm 1.4.8c)

Diagonal matrix – def: all entries 0 except on main diagonal.

Inverse of a diagonal matrix: Take reciprocals: (D^–1)_ii = 1 / (D)_ii

Powers of a diagonal matrix: Take same power of each element: (D^k)_ii = (D)_ii^k

Mult by a diagonal matrix

1. D on the left: Mult row 1 by d1, row 2 by d2, ...

2. D on the right: Mult col 1 by d1, col 2 by d2, ...

Triangular matrices

Upper triangular ("UT"): all entries below the main diagonal are 0

Lower triangular ("LT"): all entries above the main diagonal are 0

Notice: a diagonal matrix is both UT and LT

Thm 1

LT^T is UT and UT^T is LT

LT*LT is LT and UT*UT is UT

Inverse of UT or LT exists if and only if (iff) diagonal entries are all non-zero

LT^–1 is LT and UT^–1 is UT

Symmetric matrices: Def: A = A^T

(that is, they are symmetric across the main diagonal)

Thm 2: If A and B are symmetric and the same size, then

A^T is symmetric

A + B and A – B are symmetric

kA is symmetric

Thm (unnumbered) Usually, the product of matrices is not symmetric. Also, usually, matrix multiplication is not commutative. However, the product of two symmetric matrices is symmetric if and only if the multiplication is commutative, for if both conditions are true, we get:

(AB)^T = B^TA^T = BA = AB

Thm 3: If A is an invertible symmetric matrix, then A^–1 is symmetric

Proof: Assume A is invertible and symmetric. We need to show (A^–1)^T = A^–1.

Since A is invertible, by Thm 1.4.10 we have (A^–1)^T = (A^T)^–1, and since A is symmetric, we have (A^T)^–1 = A^–1.

Fact: Regardless of the dimension of A, the products AA^T and A^TA are always symmetric, as proven before Example 6 and demonstrated in Example 6 in the text.

Thm 4: In the special case where A is square and invertible, then the products AA^T and A^TA are also invertible. Proof in text.

Return to:  Merced College; Don Power               Updated 02/02/07 by Don Power