Chapter 1

1.1 Systems of Linear Equations

A linear equation in the variables x₁, ..., x_n is an equation that can be written in the form a₁x₁ + a₂x₂ + ... + a_nx_n = b where b and the coefficients a₁, ..., a_n are real or complex numbers. The subscript n may be any positive integer.

A system of linear equations (or a linear system) is a collection of one or more linear equations involving the same variables - say, x₁, ..., x_n.

A solution of the system is a list (s₁, s₂, ..., s_n) of numbers that makes each equation a true statement when the values s₁, ..., s_n are substituted for x₁, ..., x_n, respectively.

The set of all possible solutions is called the solution set of the linear system. Two linear systems are called equivalent if they have the same solution set.

A system of linear equations has

1. no solution, or
2. exactly one solution, or
3. infinitely many solutions.

A system of linear equations is said to be consistent if it has either one solution or infinitely many solutions; a system is inconsistent if it has no solution.

The essential information of a linear system can be recorded compactly in a rectangular array called a matrix. Given the system with the coefficients of each variable aligned in the columns, the matrix is called the coefficient matrix (or matrix of coefficients) of the system. An augmented matrix of a system consists of the coefficient matrix with an added column containing the constants from the right sides of the equations.

The size of a matrix tells how many rows and columns it has. An m x n matrix is a rectangular array of numbers with m rows and n columns.

Elementary Row Operations

1. (Replacement) Replace one row by the sum of itself and a multiple of another row.
2. (Interchange) Interchange two rows.
3. (Scaling) Multiply all entries in a row by a nonzero constant.

Two matrices are called row equivalent if there is a sequence of elementary row operations that transforms one matrix into the other.

If the augmented matrices of two linear systems are row equivalent, then the two systems have the same solution set.

Two Fundamental Questions about a Linear System

1. Is the system consistent; that is, does at least one solution exist?
2. If a solution exists, is it the only one; that is, is the solution unique?

1.2 Row Reduction and Echelon Forms

A rectangular matrix is in echelon form (or row echelon form) if it has the following three properties:

1. All nonzero rows are above any rows of all zeros.
2. Each leading entry of a row is in a column to the right of the leading entry of the row above it.
3. All entries in a column below a leading entry are zeros.

If a matrix in echelon form satisfies the following additional conditions, then it is in reduced echelon form (or reduced row echelon form):

4. The leading entry in each nonzero row is 1.
5. Each leading 1 is the only nonzero entry in its column.

Any nonzero matrix may be row reduced (that is, transformed by elementary row operations) into more than one matrix in echelon form, using different sequences of row operations.

Uniqueness of the Reduced Echelon Form
Each matrix is row equivalent to one and only one reduced echelon matrix.

A pivot position in a matrix A is a location in A that corresponds to a leading 1 in the reduced echelon form of A. A pivot column is a column of A that contains a pivot position.

A pivot is a nonzero number in a pivot position that is used as needed to create zeros via row operations.

The variables corresponding to the pivot columns in the matrix are called basic variables. The other variables are called free variables.

Existence and Uniqueness Theorem
A linear system is consistent if and only if the rightmost column of the augmented matrix is not a pivot column - that is, if and only if an echelon form of the augmented matrix has no row of the form [0 ... 0 b] with b nonzero. If a linear system is consistent, then the solution set contains either (i) a unique solution, when there are no free variables, or (ii) infinitely many solutions, when there is at least one free variable.

1.3 Vector Equations

A matrix with only one column is called a column vector, or simply a vector. Two vectors in R2 are equal if and only if their corresponding entries are equal.

Given two vectors u and v, their sum is the vector u+v obtained by adding corresponding entries of u and v.

Given a vector u and a real number c, the scalar multiple of u by c is the vector cu obtained by multiplying each entry in u by c.

If n is a positive integer, Rⁿ (read "r-n") denotes the collection of all lists of n real numbers, usually written as n x 1 column matrices.

The vector whose entries are all zero is called the zero vector and is denoted by 0.

Algebraic Properties of Rⁿ
For all u, v, w, in Rⁿ and all scalars c and d:
(i) u + v = v + u
(ii) (u + v) + w = u + (v + w)
(iii) u + 0 = 0 + u = u
(iv) u + (-u) = -u + u = 0 where -u denotes (-1)u
(v) c(u + v) = cu + cv
(vi) (c + d)u = cu + du
(vii) c(du) = (cd)u
(viii) 1u = u

Given vectors v₁, v₂, ..., v_p in Rⁿ and given scalars c₁, c₂, ..., c_p, the vector y defined by y = c₁v₁ + ... c_pv_p is called a linear combination of v₁, ..., v_p with weights c₁, ..., c_p.

A vector equation x₁a₁ + x₂a₂ + ... + x_na_n = b has the same solution set as the linear system whose augmented matrix is [a₁ a₂ ... a_n b]. In particular, b can be generated by a linear combination of a₁, ..., a_n if and only if there exists a solution to the linear system corresponding to the matrix.

If v₁, ..., v_p are in Rⁿ, then the set of all linear combinations of v₁, ..., v_p are denoted by span{v₁, ..., v_p} and is called the subset of Rⁿ spanned (or generated) by v₁, ..., v_p. That is, span{v₁, ..., v_p} is the collection of all vectors that can be written in the form c₁v₁ + c₂v₂ + ... + c_pv_p with c₁, ..., c_p scalars.

1.4 The Matrix Equation Ax = b

If A is an m x n matrix, with columns a₁, ..., a_n, and if x is in Rⁿ, 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.

If A is an m x n matrix, with columns a₁, ..., a_n, and if b is in R^m, the matrix equation Ax = b has the same solution set as the vector equation x₁a₁ + x₂a₂ + ... + x_na_n = b which, in turn, has the same solution set as the system of linear equations whose augmented matrix is [ a₁ a₂ ... a_n b ].

The equation Ax = b has a solution if and only if b is a linear combination of the columns of A.

Let A be an m x n matrix. Then the following statements are logically equivalent. That is, for a particular A, either they are all true statements or they are 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.
d. A has a pivot position in every row.

If A is an m x n matrix, u and v are vectors in Rⁿ, and c is a scalar, then
a. A(u + v) = Au + Av.
b. A(cu) = c(Au).

1.5 Solution Sets of Linear Systems

A system of linear equations is said to be homogenous if it can be written in the form Ax = 0, where A is an m x n matrix and 0 is the zero vector in R^m. Such a system Ax = 0 always has at least one solution, namely, x = 0 (the zero vector in Rⁿ). This zero solution is usually called the trivial solution. For a given equation Ax = 0, the important question is whether there exists a nontrivial solution, that is, a nonzero vector x that satisfies Ax = 0.

The homogenous equation Ax = 0 has a nontrivial solution if and only if the equation has at least one free variable.

Whenever a solution set is described explicitly with vectors, we say that the solution is in parametric vector form.

Suppose the equation Ax = b is consistent for some given b, and let p be a solution. Then the solution set of Ax = b is the set of all vectors of the form w = p + v_h, where v_h is any solution of the homogenous equation Ax = 0.

1.7 Linear Independence

An indexed set of vectors {v₁, ..., v_p} in Rⁿ is said to be linearly independent if the vector equation x₁v₁ + x₂v₂ + ... + x_pv_p = 0 has only the trivial solution. The set {v₁, ..., v_p} is said to be linearly dependent if there exist weights c₁, ..., c_p, not all zero, such that c₁v₁ + c₂v₂ + ... + c_pv_p = 0.

The columns of a matrix A are linearly independent if and only if the equation Ax = 0 has only the trivial solution.

A set of two vectors {v₁, v₂} is linearly dependent if at least one of the vectors is a multiple of the other. The set is linearly independent if and only if neither of the vectors is a multiple of the other.

Characterization of Linearly Dependent Sets
An indexed set S = {v₁, ..., v_p} of two or more vectors is linearly dependent if and only if at least one of the vectors in S is a linear combination of the others. In fact, if S is linearly dependent and v₁ is not equal to 0, then some v_j (with j > 1) is a linear combination of the preceding vectors, v₁, ..., v_j-1.

If a set contains more vectors than there are entries in each vector, then the set is linearly dependent. That is, any set {v₁, ..., v_p} in Rⁿ is linearly dependent if p > n.

If a set S = {v₁, ..., v_p} in Rⁿ contains the zero vector, then the set is linearly dependent.

1.8 Introduction to Linear Transformations

A transformation(or function or mapping) T from Rⁿ to R^m is a rule that assigns to each vector x in Rⁿ a vector T(x) in R^m.

The set Rⁿ is called the domain of T, and R^m is called the codomain of T.

For x in Rⁿ, the vector T(x) in R^m is called the image of x(under the action of T).

The set of all images T(x) is called the range of T.

A transformation(or mapping) T is linear if:
(i) T(u + v) = T(u) + T(v) for all u, v in the domain of T.
(ii) T(cu) = cT(u) for all scalars c and all u in the domain of T.

If T is a linear transformation, then T(0) = 0 and T(cu + dv) = cT(u) + dT(v) for all vectors u, v in the domain of T and all scalars c, d.

Repeated action of the above property produces a useful generalization:
T(c₁v₁ + ... + c_pv_p) = c₁T(v₁) + ... + c_pT(v_p)
_{Note: This is sometimes referred to as a superposition principle.}

1.9 The Matrix of a Linear Transformation

Let T : Rⁿ → R^m be a linear transformation. Then there exists a unique matrix A such that T(x) = Ax for all x in Rⁿ.
In fact, A is the m x n matrix whose jth column is the vector T(e_j), where e_j is the jth column of the identity matrix in Rⁿ:
A = [T(e₁) ... T(e_n) ]. This matrix A is called the standard matrix for the linear transformation T.
_{Note: The term linear transformation focuses on a property of a mapping, while matrix transformation describes how such a mapping is implemented.}

A mapping T: Rⁿ → R^m is said to be onto R^m if each b in R^m is the image of at least one x in Rⁿ.

A mapping T: Rⁿ → R^m is said to be one-to-one R^m if each b in R^m is the image of at most one x in Rⁿ.

Let T: Rⁿ → R^m be a linear transformation. Then T is one-to-one if and only if the equation T(x) = 0 has only the trivial solution.

Let T: Rⁿ → R^m be a linear transformation, and let A be the standard matrix for T. Then:
a. T maps Rⁿ onto R^m if and only if the columns of A span R^m.
b. T is one-to-one if and only if the columns of A are linearly independent.