Please enable JavaScript.

Coggle requires JavaScript to display documents.

General Vector Spaces, The Steps, The Steps - Coggle Diagram

- - - - Step 1: identify the set V of objects that will become
        vectors.
        Step 2: Identify the addition and scalar
        multiplication operations on V
        Step 3: Verify Axioms 1 and 6; that is, adding two
        vectors in V produces a vector in V and
        multiplying a vector in V by a scalar also
        produces a vector in V.
        Step 4: Confirm that Axioms 2, 3, 4, 5, 6, 7, 8, 9
        and 10.
- - - - Axiom 1—Closure of W under addition
      - Axiom 4—Existence of a zero vector in W
      - Axiom 5—Existence of a negative in W for every vector in W
      - Axiom 6—Closure of W under scalar multiplication
- - - - THEOREM 5.1.1
        If A is an n x n matrix, then λ is an eigenvalue of A if and only if it satisfies the equation:
        det( λI-A) = 0
        This is called the characteristic equation of A.
      - THEOREM 5.1.2
        If A is an n x n triangular matrix (upper triangular, lower triangular, or diagonal), then the eigenvalues of A are the entries on the main diagonal of A.
      - THEOREM 5.1.3 If A is an n x n matrix, the following statements are equivalent.
        (a) λ is an eigenvalue of A.
        (b) The system of equations (λI-A)x = 0 has nontrivial solutions.
        (c) There is a nonzero vector x such that Ax = λx.
        d) λ is a solution of the characteristic equation det(λI-A) = 0.
      - THEOREM 5.1.4
        If k is a positive integer, λ is an eigenvalue of a matrix A, and x is a corresponding eigenvector, then λ^(k) is an eigenvalue of A^(k) and x is a corresponding eigenvector.
      - THEOREM 5.1.5
        A square matrix A is invertible if and only if λ= 0 is not an eigenvalue of A.
    - - Similarity:
        If A and B are square matrices, then we say that B is similar to A if there is an invertible matrix P such that
        B = P^(-1)AP.
      - Diagonalizable
        A square matrix A is said to be diagonalizable if it is similar to some diagonal matrix; that is, if there exists an invertible matrix P such that is diagonal. In this case the matrix P is said to diagonalize A.
      - THEOREM 5.2.1
        If A is an n x n matrix, the following statements are equivalent.
        (a) A is diagonalizable.
        (b)A has n linearly independent eigenvectors.
      - THEOREM 5.2.2
        a) If λ1, λ2, …, λk are distinct eigenvalues of a matrix A, and if v1, v2, …, vk are corresponding eigenvectors, then {v1, v2, …, vk} is a linearly independent set.
        b) An n × n matrix with n distinct eigenvalues is diagonalizable.
        Remark Part (a) of Theorem 5.2.2 is a special case of a more general result: Specifically, if λ1, λ2, …, λk are distinct eigenvalues, and if S1, S2, …, Sk are corresponding sets of linearly independent eigenvectors, then the union of these sets is linearly independent.
        
        A Procedure for Diagonalizing an n × n Matrix
        Step 1. Determine first whether the matrix is actually diagonalizable by searching for n linearly independent eigenvectors. One way to do this is to find a basis for each eigenspace and count the total number of vectors obtained. If there is a total of n vectors, then the matrix is diagonalizable, and if the total is less than n, then it is not.
        Step 2. If you ascertained that the matrix is diagonalizable, then form the matrix whose column vectors are the n basis vectors you obtained in Step 1.
        Step 3. P −1AP will be a diagonal matrix whose successive diagonal entries are the eigenvalues λ1, λ2, …, λn that correspond to the successive columns of P.
      - THEOREM 5.2.3
        If k is a positive integer, λ is an eigenvalue of a matrix A, and x is a corresponding eigenvector, then λ^(k) is an eigenvalue of A^(k) and x is a corresponding eigenvector.
      - THEOREM 5.2.4
        If A is a square matrix, then:
        (a)For every eigenvalueof A, the geometric multiplicity is less than or equal to the algebraic multiplicity.
        (b)A is diagonalizable if and only if the geometry multiplicity of every eigenvalueis equal to the algebraic multiplicity.
    - - Definition 1
        If n is a positive integer, then a complex n‐tuple is a sequence of n complex numbers (V1, V2, …,Vn). The set of all complex n‐tuples is called complex n‐space and is denoted by C n. Scalars are complex numbers, and the operations of addition, subtraction, and scalar multiplication are performed componentwise.
      - Definition 2
        If u = (u1, u2, …, un) and v = (v1, v2, ..., vn) are vectors in C^(n), then the complex Euclidean inner product of u and v (also called the complex dot product) is denoted by u · v and is defined as
        
        We also define the Euclidean norm on C^(n) to be
      - Theorem 5.3.1
        If u and v are vectors in C n, and if k is a scalar, then:
      - Theorem 5.3.2
        If A is an m × k complex matrix and B is a k × n complex matrix, then:
      - Theorem 5.3.3
        If u, v, and w are vectors in C n, and if k is a scalar, then the complex Euclidean inner product has the following properties:
        
        Proof (d)
      - Theorem 5.3.4
        If λ is an eigenvalue of a real n × n matrix A, and if x is a corresponding eigenvector, then λ is also an eigenvalue of A, and x is a corresponding eigenvector.
        Proof
        Since λ is an eigenvalue of A and x is a corresponding eigenvector, we have
        
        However, A` = A since A has real entries, so it follows from part (c) of Theorem 5.3.2 that
        
        Both equations together imply that
        
        in which xnot equal to 0 (why?). This tells us that λ is an eigenvalue of A and x` is a corresponding eigenvector.
      - Theorem 5.3.5
        If A is a 2 × 2 matrix with real entries, then the characteristic equation of A is λ^(2) − tr(A)λ + det(A) = 0 and
        a) A has two distinct real eigenvalues if tr(A)^(2) − 4det(A) > 0;
        b) A has one repeated real eigenvalue if tr(A)^(2) − 4det(A) = 0;
        c) A has two complex conjugate eigenvalues if tr(A)^(2) − 4det(A) < 0.
      - Theorem 5.3.6
        If A is a real symmetric matrix, then A has real eigenvalues.
        Proof
        Suppose that λ is an eigenvalue of A and x is a corresponding eigenvector, where we allow for the possibility that λ is complex and x is in C^(n). Thus,
        Ax = λx
        where x ≠ 0. If we multiply both sides of this equation by and use the fact that
        
        then we obtain
        
        Since the denominator in this expression is real, we can prove that λ is real by showing that
        
        But A is symmetric and has real entries, so it follows from the second equality and properties of the conjugate that
        
        =
      - Theorem 5.3.7
        The eigenvalues of the real matrix
        
        are λ = a ± bi. If a and b are not both zero, then this matrix can be factored as
        
        where ϕ is the angle from the positive x‐axis to the ray that joins the origin to the point (a, b)
        
        Geometrically, this theorem states that multiplication by a matrix of form (15) can be viewed as a rotation through the angle ϕ followed by a scaling with factor |λ|
        
        Proof
        The characteristic equation of C is (λ − a)^(2) + b^(2) = 0 (verify), from which it follows that the eigenvalues of C are λ = a ± bi. Assuming that a and b are not both zero, let ϕ be the angle from the positive x‐axis to the ray that joins the origin to the point (a, b). The angle ϕ is an argument of the eigenvalue λ = a + bi, so we see that
        
        It follows from this that the matrix can be written as
      - Theorem 5.3.8
        Let A be a real 2 × 2 matrix with complex eigenvalues λ = a ± bi (where b ≠ 0). If x is an eigenvector of A corresponding to λ = a − bi, then the matrix P = [Re(x) Im(x)] is invertible and
    - - Terminology
        Recall from calculus that a differential equation is an equation involving unknown functions and their derivatives. The order of a differential equation is the order of the highest derivative it contains. The simplest differential equations are the first‐order equations of the form
        
        where y = f(x) is an unknown differentiable function to be determined, y ′ = dy/dx is its derivative, and a is a constant. As with most differential equations, this equation has infinitely many solutions; they are the functions of the form
        
        where c is an arbitrary constant. That every function of this form is a solution follows from the computation
        
        and that these are the only solutions is shown in the exercises. As an example, the general solution of the differential equation y ′ = 5y is
        
        Often, a physical problem that leads to a differential equation imposes some conditions that enable us to isolate one particular solution from the general solution. For example, if we require that solution (3) of the equation y ′ = 5y satisfy the added condition
        
        (that is, y = 6 when x = 0), then on substituting these values in (3), we obtain 6 = ce0 = c, from which we conclude that
        
        is the only solution y ′ = 5y that satisfies.
        A condition, which specifies the value of the general solution at a point, is called an initial condition, and the problem of solving a differential equation subject to an initial condition is called an initial‐value problem.
      - First‐Order Linear Systems
        In this section we will be concerned with solving systems of differential equations of the form
        
        where y1 = f1(x), y2 = f2(x), …, yn = fn(x) are functions to be determined, and the aij's are constants. In matrix notation, can be written as
        
        or more briefly as
        
        where the notation y ′ denotes the vector obtained by differentiating each component of y.
        We call or its matrix form a constant coefficient first‐order homogeneous linear system. It is of first order because all derivatives are of that order, it is linear because differentiation and matrix multiplication are linear transformations, and it is homogeneous because
        
        is a solution regardless of the values of the coefficients. As expected, this is called the trivial solution. In this section we will work primarily with the matrix form. Here is an example.
      - A Procedure for Solving y ′ = Ay If A Is Diagonalizable
        Step 1. Find a matrix P that diagonalizes A.
        Step 2. Make the substitutions y = Pu and y ′ = Pu ′ to obtain a new “diagonal system” u ′ = Du, where D = P ^(−1) AP.
        Step 3. Solve u ′ = Du.
        Step 4. Determine y from the equation y = Pu.
    - - Dynamical Systems
        A dynamical system is a finite set of variables whose values change with time. The value of a variable at a point in time is called the state of the variable at that time, and the vector formed from these states is called the state vector (or state) of the dynamical system at that time. Our primary objective in this section is to analyze how the state vector of a dynamical system changes with time.
      - A Markov chain is a dynamical system whose state vectors at a succession of equally spaced times are probability vectors and for which the state vectors at successive times are related by an equation of the form
        
        in which P = [pij] is a stochastic matrix and pij is the probability that the system will be in state i at time t = k + 1 if it is in state j at time t = k. The matrix P is called the transition matrix for the system
      - Markov Chains in Terms of Powers of the Transition Matrix
        In a Markov chain with an initial state of x(0), the successive state vectors are
        
        For brevity, it is common to denote x(k) by xk, which allows us to write the successive state vectors more briefly as
        
        Alternatively, these state vectors can be expressed in terms of the initial state vector x0 as
        
        from which it follows that
      - A stochastic matrix P is said to be regular if P or some positive power of P has all positive entries, and a Markov chain whose transition matrix is regular is said to be a regular Markov chain.
      - Theorem 5.5.1
        If P is the transition matrix for a regular Markov chain, then:
        a)There is a unique probability vector q with positive entries such that Pq = q.
        b)For any initial probability vector x0, the sequence of state vectors
        
        converges to q.
        c)The sequence P, P^(2), …, P^(k), … converges to the matrix Q each of whose column vectors is q.
  - - - In 2-D: ax + by = c
        In 3-D: ax + by + cz = d
        Generally:
      - A general linear system of m equations with n unknowns can be written as:
      - Linear System with Two and Three Unknowns
        
        Two Unknowns
        
        Consider the linear system:
        
        Three Unknowns
        
        In general, we say that a linear system is consistent if it has at least one solution and inconsistent if it has no solutions.
    - - What is Echelon Form?
        
        Echelon Forms
        
        If a row does not consist entirely of zero, then the first nonzero number in the row is a '1'
        (called a leading 1)
        
        If there are any rows that consist entirely of zeros, then they are grouped together at the bottom of the matrix.
        
        In any two successive rows that do not consist entirely of zeros, the leading 1 in the lower row occurs farther to the right than the leading 1 in the higher row.
        
        Each column that contains a leading 1 has zeros everywhere else in that column
      - Examples
        
        Row Echelon Form
        
        Reduced Row Echelon Form
      - We convert a matrix to Echelon Form Matrix by using Gaussian Elimination
      - The Steps
        
        1 more item...
      - Homogeneous Linear System
      - The Definition and Theorems:
    - - Definition
      - Types of Matrices
      - Operations on Matrices
        
        Definitions
        
        Equality of Matrices
        
        Addition & Subtraction
        
        Scalar Multiplication
        
        Matrix Multiplication
        
        Transpose of a Matrix
        
        Trace of a Matrix
        
        Partitioned Matrices
        
        Matrix Multiplication by Columns and by Rows
        
        Matrix Products as Linear Combinations
        
        Definition
        
        Theorem
    - - Definition
      - Theorem
      - Properties
    - - Definition
      - Theorem
    - - Diagonal Matrices
        
        General n x n diagonal matrix
        
        (1)
        
        Invertible diagonal matrix
        
        Powers of diagonal matrix
      - Triangular Matrices
        
        Theorem
      - Symmetric Matrices
        
        Theorem
    - - Theorem
    - - i) Network Analysis
        
        A network is a set of branches through which something "flows"
        
        Example: Electrical wires, pipe, traffic lanes or economic linkages
        
        Nodes or junctions: points where branches meet
        
        In the study of networks, there is generally some numerical measure of the rate at which the medium flows through a branch
        
        Our attention to networks: flow conservation at each node
        
        Example
        
        The rate of flow into any node is equal to the rate of flow out of that node
        
        Example
      - ii) Design of Traffic Patterns
        
        Example
      - iii) Electrical Circuits
        
        Example
      - iv) Chemical Equations
        
        Example
      - v) Polynomial Interpolation
        
        Example
    - - i) Economic Modelling
      - Use Matrix methods to study the relationships between different sectors in an economy
      - Inputs and outputs are commonly measured in monetary units
      - The ideas that has been developed by Leontief:
        
        Inputs and outputs in an Economy
        
        Leontief Model of an Open Economy
        
        Productive Open Economies
      - The Formula !!
  - - - Note that the signs of the cofactors follow a “checkerboard pattern.
      - and that the inverse of A can be expressed in terms of the determinant as
      - is invertible if and only if ad − bc ≠ 0 and that the expression ad − bc is called the determinant of the matrix A
      - Example :
        
        cofactor for c11 is -
      - THEOREM
        -If A is an n × n triangular matrix (upper triangular, lower triangular, or diagonal), then det(A) is the product of the entries on the main diagonal of the matrix; that is, det(A) = a11a22 ⋯ ann.
        -If A is an n × n matrix, then regardless of which row or column of A is chosen, the number obtained by multiplying the entries in that row or column by the corresponding cofactors and adding the resulting products is always the same.
    - - If A is an n × n matrix, then the following statements are equivalent.
        (a) A is invertible.
        (b) Ax = 0 has only the trivial solution.
        (c) The reduced row echelon form of A is In.
        (d) A can be expressed as a product of elementary matrices.
        (e) Ax = b is consistent for every n × 1 matrix b.
        (f) Ax = b has exactly one solution for every n × 1 matrix b.
        (g) det(A) ≠ 0.
    - - Let A be a square matrix. If A has a row of zeros or a column of zeros, then det(A) = 0.
      - Let A be a square matrix. Then det(A) = det(ATranspose).
      - Let A be an n × n matrix.
      - (a) If B is the matrix that results when a single row or single column of A is multiplied by a scalar k, then det(B) = k det(A).
      - (b) If B is the matrix that results when two rows or two columns of A are interchanged, then det(B) = −det(A).
      - (c) If B is the matrix that results when a multiple of one row of A is added to another or when a multiple of one column is added to another, then det(B) = det(A).
      - Let E be an n × n elementary matrix.
      - (a) If E results from multiplying a row of In by a nonzero number k, then det(E) = k.
      - (b) If E results from interchanging two rows of In, then det(E) = −1.
      - (c) If E results from adding a multiple of one row of In to another, then det(E) = 1.
  - - - An inner product on a real vector space V is a function that associates a real number 〈u, v〉 with each pair of vectors in V in such a way that the following axioms are satisfied for all vectors u, v, and w in V and all scalars k.
        
        A real vector space with an inner product is called a real inner product space.
      - If V is a real inner product space, then the norm (or length) of a vector v in V is denoted by ‖v‖ and is defined by
        
        and the distance between two vectors is denoted by d(u, v) and is defined by
        
        A vector of norm 1 is called a unit vector
      - Theorem 6.1.1
        If u and v are vectors in a real inner product space V, and if k is a scalar, then:
        ‖v‖ ≥ 0 with equality if and only if v = 0.
        ‖kv‖ = |k|‖v‖.
        d(u, v) = d(v, u).
        d(u, v) ≥ 0 with equality if and only if u = v.
      - If V is an inner product space, then the set of points in V that satisfy
        ||u|| = 1
        is called the unit sphere in V (or the unit circle in the case where V = R^(2)).
      - Theorem 6.1.2
        If u, v, and w are vectors in a real inner product space V, and if k is a scalar, then:
        〈0, v〉 = 〈v, 0〉 = 0
        〈u, v + w〉 = 〈u, v〉 + 〈u, w〉
        〈u, v − w〉 = 〈u, v〉 − 〈u, w〉
        〈u − v, w〉 = 〈u, w〉 − 〈v, w〉
        k〈u, v〉 = 〈u, kv〉
        Proof We will prove part (b) and leave the proofs of the remaining parts for the reader.
        
        The following example illustrates how Theorem 6.1.2 and the defining properties of inner products can be used to perform algebraic computations with inner products. As you read through the example, you will find it instructive to justify the steps.
    - - Theorem 6.2.1
        Cauchy–Schwarz Inequality If u and v are vectors in a real inner product space V, then
        
        Proof We warn you in advance that the proof presented here depends on a clever trick that is not easy to motivate. In the case where u = 0 the two sides of (3) are equal since 〈u, v〉 and ‖u‖ are both zero. Thus, we need consider only the case where u ≠ 0. Making this assumption, let
        
        and let t be any real number. Since the positivity axiom states that the inner product of any vector with itself is nonnegative, it follows that
        
        This inequality implies that the quadratic polynomial at2 + bt + c has either no real roots or a repeated real root. Therefore, its discriminant must satisfy the inequality b2 − 4ac ≤ 0. Expressing the coefficients a, b, and c in terms of the vectors u and v gives
        
        or, equivalently,
        
        Taking square roots of both sides and using the fact that 〈u, u〉 and 〈v, v〉 are nonnegative yields
        
        which completes the proof.
      - Theorem 6.2.2
        If u, v, and w are vectors in a real inner product space V, and if k is any scalar, then:
        (a) ‖u + v‖ ≤ ‖u‖ + ‖v‖ [Triangle inequality for vectors]
        (b) d(u, v) ≤ d(u, w) + d(w, v) [Triangle inequality for distances]
        Proof (a)
        
        Taking square roots gives ‖u + v‖ ≤ ‖u‖ + ‖v‖.
        Proof (b)
        Identical to the proof of part (b) of Theorem 3.2.5.
      - Definition 1
        Two vectors u and v in an inner product space V called orthogonal if 〈u, v〉 = 0.
      - Theorem 6.2.3
        Generalized Theorem of Pythagoras If u and v are orthogonal vectors in a real inner product space, then
        
        Proof The orthogonality of u and v implies that 〈u, v〉 = 0, so
      - Definition 2
        If W is a subspace of a real inner product space V, then the set of all vectors in V that are orthogonal to every vector in W is called the orthogonal complement of W and is denoted by the symbol W ⊥.
      - Theorem 6.2.4
        If W is a subspace of a real inner product space V, then:
        W ⊥ is a subspace of V.
        W ∩ W ⊥ = {0}.
        Proof (a)
        The set W ⊥ contains at least the zero vector, since 〈0, w〉 = 0 for every vector w in W. Thus, it remains to show that W ⊥ is closed under addition and scalar multiplication. To do this, suppose that u and v are vectors in W ⊥, so that for every vector w in W we have 〈u, w〉 = 0 and 〈v, w〉 = 0. It follows from the additivity and homogeneity axioms of inner products that
        
        which proves that u + v and ku are in W ⊥. Proof (b) If v is any vector in both W and W ⊥, then v is orthogonal to itself; that is, 〈v, v〉 = 0. It follows from the positivity axiom for inner products that v = 0.
      - Theorem 6.2.5
        If W is a subspace of a real finite‐dimensional inner product space V, then the orthogonal complement of W ⊥ is W; that is,
    - - Definition 1
        A set of two or more vectors in a real inner product space is said to be orthogonal if all pairs of distinct vectors in the set are orthogonal. An orthogonal set in which each vector has norm 1 is said to be orthonormal.
      - Theorem 6.3.1
        If S = {v1, v2, …, vn} is an orthogonal set of nonzero vectors in an inner product space, then S is linearly independent. Proof Assume that
        
        To demonstrate that S = {v1, v2, …, vn} is linearly independent, we must prove that
        
        For each vi in S, it follows that
        
        or, equivalently,
        
        From the orthogonality of S it follows that 〈vj, vi〉 = 0 when j ≠ i, so this equation reduces to
        
        Since the vectors in S are assumed to be nonzero, it follows from the positivity axiom for inner products that 〈vi, vi〉 ≠ 0. Thus, the preceding equation implies that each ki in Equation (2) is zero, which is what we wanted to prove.
      - Theorem 6.3.2
        If S = {v1, v2, …, vn} is an orthogonal basis for an inner product space V, and if u is any vector in V, then
        
        If S = {v1, v2, …, vn} is an orthonormal basis for an inner product space V, and if u is any vector in V, then
        
        Proof (a) Since S = {v1, v2, …, vn} is a basis for V, every vector u in V can be expressed in the form
        
        We will complete the proof by showing that
        
        for i = 1, 2, …, n. To do this, observe first that
        
        Since S is an orthogonal set, all of the inner products in the last equality are zero except the ith, so we have
        
        Solving this equation for ci yields (5), which completes the proof. Proof (b) In this case, ‖v1‖ = ‖v2‖ = ⋯ = ‖vn‖ = 1, so Formula (3) simplifies to Formula (4).
      - Theorem 6.3.3
        Projection Theorem
        If W is a finite‐dimensional subspace of an inner product space V, then every vector u in V can be expressed in exactly one way as
        
        where w1 is in W and w2 is in W ⊥.
      - Theorem 6.3.4
        Let W be a finite‐dimensional subspace of an inner product space V.
        If {v1, v2, …, vr} is an orthogonal basis for W, and u is any vector in V, then
        
        If {v1, v2, …, vr} is an orthonormal basis for W, and u is any vector in V, then
        
        Proof (a)
        It follows from Theorem 6.3.3 that the vector u can be expressed in the form u = w1 + w2, where w1 = projWu is in W and w2 is in W ⊥ and it follows from Theorem 6.3.2 that the component projWu = w1 can be expressed in terms of the basis vectors for W as
        
        Since w2 is orthogonal to W, it follows that
        
        so we can rewrite as
        
        or, equivalently, as
        
        Proof (b)
        In this case, ‖v1‖ = ‖v2‖ = ⋯ = ‖vr‖ = 1, so Formula (14) simplifies to Formula (13).
      - Theorem 6.3.5
        Every nonzero finite‐dimensional inner product space has an orthonormal basis.
        Proof Let W be any nonzero finite‐dimensional subspace of an inner product space, and suppose that {u1, u2, …, ur} is any basis for W. It suffices to show that W has an orthogonal basis since the vectors in that basis can be normalized to obtain an orthonormal basis. The following sequence of steps will produce an orthogonal basis {v1, v2, …, vr} for W:
        Step 1. Let v1 = u1.
        Step 2. As illustrated in Figure 6.3.3, we can obtain a vector v2 that is orthogonal to v1 by computing the component of u2 that is orthogonal to the space W1 spanned by v1. Using Formula (12) to perform this computation, we obtain
        
        Of course, if v2 = 0, then v2 is not a basis vector. But this cannot happen, since it would then follow from the preceding formula for v2 that
        
        which implies that u2 is a multiple of u1, contradicting the linear independence of the basis {u1, u2, …, ur}. FIGURE 6.3.3
        
        Step 3. To construct a vector v3 that is orthogonal to both v1 and v2, we compute the component of u3 orthogonal to the space W2 spanned by v1 and v2 (Figure 6.3.4). Using Formula (12) to perform this computation, we obtain
        
        As in Step 2., the linear independence of {u1, u2, …, ur} ensures that v3 ≠ 0. We leave the details for you. FIGURE 6.3.4
        Step 4. To determine a vector v4 that is orthogonal to v1, v2, and v3, we compute the component of u4 orthogonal to the space W3 spanned by v1, v2, and v3. From (12),
        
        Continuing in this way we will produce after r steps an orthogonal set of nonzero vectors {v1, v2, …, vr}. Since such sets are linearly independent, we will have produced an orthogonal basis for the r‐dimensional space W. By normalizing these basis vectors we can obtain an orthonormal basis.
      - Theorem 6.3.6
        If W is a finite‐dimensional inner product space, then:
        Every orthogonal set of nonzero vectors in W can be enlarged to an orthogonal basis for W.
        Every orthonormal set in W can be enlarged to an orthonormal basis for W.
        Proof (b)
        Suppose that S = {v1, v2, …, vs} is an orthonormal set of vectors in W. Part (b) of Theorem 4.6.5 tells us that we can enlarge S to some basis
        
        for W. If we now apply the Gram–Schmidt process to the set S′, then the vectors v1, v2, …, vs, will not be affected since they are already orthonormal, and the resulting set
        
        will be an orthonormal basis for W.
      - Theorem 6.3.7
        QR‐Decomposition If A is an m × n matrix with linearly independent column vectors, then A can be factored as
        
        where Q is an m × n matrix with orthonormal column vectors, and R is an n × n invertible upper triangular matrix.
    - - Theorem 6.4.1
        Best Approximation Theorem If W is a finite‐dimensional subspace of an inner product space V, and if b is a vector in V, then proj Wb is the best approximation to b from W in the sense that
        
        for every vector w in W that is different from projWb.
        Proof
        For every vector w in W, we can write
        
        But projW b − w, being a difference of vectors in W, is itself in W; and since b − projW b is orthogonal to W, the two terms on the right side of (1) are orthogonal. Thus, it follows from the Theorem of Pythagoras (Theorem 6.2.3) that
        
        If w ≠ projW b, it follows that the second term in this sum is positive, and hence that
        
        Taking square roots and using the fact that norms are nonnegative, it follows that
        
        Theorem 6.4.2
        For every linear system Ax = b, the associated normal system
        
        is consistent, and all solutions of are least squares solutions of Ax = b. Moreover, if x is any least squares solution, W is the column space of A, then
        
        Theorem 6.4.3
        If A is an m × n matrix, then the following are equivalent.The column vectors of A are linearly independent.
        ATA is invertible.
        Proof
        We will prove that (a) ⇒ (b) and leave the proof that (b) ⇒ (a) as an exercise.
        (a) ⇒ (b) Assume that the column vectors of A are linearly independent. The matrix ATA has size n × n, so we can prove that this matrix is invertible by showing that the linear system ATAx = 0 has only the trivial solution. But if x is any solution of this system, then Ax is in the null space of AT and also in the column space of A. By Theorem 4.9.7(b) these spaces are orthogonal complements, so part (b) of Theorem 6.2.4 implies that Ax = 0. But A is assumed to have linearly independent column vectors, so it follows from parts (b) and (h) of Theorem 5.1.5 x = 0.
        
        Theorem 6.4.4
        If A is an m × n matrix with linearly independent column vectors, then for every m × 1 matrix b, the linear system Ax = b has a unique least squares solution. This solution is given by
        
        Moreover, if W is the column space of A, then
        
        Theorem 6.4.5
        Equivalent Statements If A is an n × n matrix in which there are no duplicate rows and no duplicate columns, then the following statements are equivalent.
        A is invertible.
        Ax = 0 has only the trivial solution.
        The reduced row echelon form of A is In.
        A is expressible as a product of elementary matrices. Ax = b is consistent for every n × 1 matrix b.
        Ax = b has exactly one solution for every n × 1 matrix b. det(A) ≠ 0.
        The column vectors of A are linearly independent.
        The row vectors of A are linearly independent.
        The column vectors of A span Rn.
        The row vectors of A span Rn.
        The column vectors of A form a basis for Rn. The row vectors of A form a basis for Rn.
        A has rank n.
        A has nullity 0.
        The orthogonal complement of the null space of A is Rn. The orthogonal complement of the row space of A is {0}.
        λ = 0 is not an eigenvalue of A.
        ATA is invertible.
        
        Theorem 6.4.6
        If A is an m × n matrix with linearly independent column vectors, and if A = QR is a QR‐decomposition of A (see Theorem 6.3.7), then for each b in Rm the system Ax = b has a unique least squares solution given by
    - - Theorem 6.5.1
        Uniqueness of the Regression Line
        Let (x1, y1), (x2, y2), …, (xn, yn) be a set of two or more data points, not all lying on a vertical line, and let
        
        Then there is a unique least squares straight line fit
        
        to the data points. Moreover,
        
        is given by the formula
        
        which expresses the fact that v = v* is the unique solution of the normal equation
      - Least Squares Fit of a Polynomial
        
        The technique described for fitting a straight line to data points can be generalized to fitting a polynomial of specified degree to data points. Let us attempt to fit a polynomial of fixed degree m
        
        to n points
        
        Substituting these n values of x and y into (9) yields the n equations
        
        or in matrix form,
        
        where
        
        As before, the solutions of the normal equations
        
        determine the coefficients of the polynomial, and the vector v minimizes
        
        Conditions that guarantee the invertibility of MTM are discussed in the exercises. If MTM is invertible, then the normal equations have a unique solution v = v*, which is given by
    - - Best Approximations
        All of the problems that we will study in this section will be special cases of the following general problem. Approximation Problem Given a function f that is continuous on an interval [a, b], find the “best possible approximation” to f using only functions from a specified subspace W of C[a, b].
      - Measurements of Error
        
        To solve approximation problems of the preceding types, we first need to make the phrase “best approximation over [a, b]” mathematically precise. To do this we will need some way of quantifying the error that results when one continuous function is approximated by another over an interval [a, b]. If we were to approximate f(x) by g(x), and if we were concerned only with the error in that approximation at a single point x0, then it would be natural to define the error to be
        
        sometimes called the deviation between f and g at x0 (Figure 6.6.1). However, we are not concerned simply with measuring the error at a single point but rather with measuring it over the entire interval [a, b]. The difficulty is that an approximation may have small deviations in one part of the interval and large deviations in another. One possible way of accounting for this is to integrate the deviation |f(x) − g(x)| over the interval [a, b] and define the error over the interval to be
        
        FIGURE 6.6.1
        The deviation between f and g at x0.
        
        FIGURE 6.6.2
        The area between the graphs of f and g over [a, b] measures the error in approximating f by g over [a, b].
        
        Although mean square error emphasizes larger deviations because of the squaring, it has the advantage of allowing us to bring to bear the theory of inner product spaces. To see how, suppose that f is a continuous function on [a, b] that we want to approximate by a function g from a subspace W of C[a, b], and suppose that C[a, b] is given the inner product
        
        It follows that
        
        so minimizing the mean square error is the same as minimizing ‖f − g‖2. Thus, the approximation problem posed informally at the beginning of this section can be restated more precisely as follows.
      - Least Squares Approximation
        Least Squares Approximation Problem
        Let f be a function that is continuous on an interval [a, b], let C[a, b] have the inner product
        
        and let W be a finite‐dimensional subspace of C[a, b]. Find a function g in W that minimizes
        
        Since ‖f − g‖2 and ‖f − g‖ are minimized by the same function g, this problem is equivalent to looking for a function g in W that is closest to f. But we know from Theorem 6.4.1 that g = projW f is such a function (Figure 6.6.3).
      - Theorem 6.6.1 If f is a continuous function on [a, b], and W is a finite‐dimensional subspace of C[a, b], then the function g in W that minimizes the mean square error
        
        is g = projW f, where the orthogonal projection is relative to the inner product The function g = projWf is called the least squares approximation to f from W.
        
        Fourier Series
        A function of the form
        
        is called a trigonometric polynomial; if cn and dn are not both zero, then T(x) is said to have order n. For example,
        
        is a trigonometric polynomial of order 4 with
        
        It is evident from (2) that the trigonometric polynomials of order n or less are the various possible linear combinations of
        
        It can be shown that these 2n + 1 functions are linearly independent and thus form a basis for a (2n + 1)‐dimensional subspace of C[a, b].
        
        Let us now consider the problem of finding the least squares approximation of a continuous function f(x) over the interval [0, 2π] by a trigonometric polynomial of order n or less. As noted above, the least squares approximation to f from W is the orthogonal projection of f on W. To find this orthogonal projection, we must find an orthonormal basis g0, g1, …, g2n for W, after which we can compute the orthogonal projection on W from the formula
        
        [see Theorem 6.4.3(b)]. An orthonormal basis for W can be obtained by applying the Gram–Schmidt process to the basis vectors in (3) using the inner product
        
        This yields the orthonormal basis
        
        If we introduce the notation
        
        then on substituting (5) in (4), we obtain
        
        where,
        
        In short,
        
        The numbers a0, a1, …, an, b1, …, bn are called the Fourier coefficients of f.
  - - - Kernel and Range
        
        Definition 2:
        If T : V → W is a linear transformation, then the set of vectors in V that T maps into 0 is called the kernel of T and is denoted by ker(T). The set of all vectors in W that are images under T of at least one vector in V is called the range of T and is denoted by R(T).
        
        Properties
      - Rank and Nulity
        
        Properties
  - - - Definition
        
        Method
      - Theorem
      - Bookkeeping
    - - Definition
      - Theorem
      - Euclidean Scaling
      - Maximum Entry Scaling
- - - - 4.4 Linear Independence
        
        Let S = {v1, v2, …, vr} be a set of vectors in Rn. If r > n, then S is linearly dependent.
        
        Suppose that
        v1 + (v11 ,v12 ,...,v1n)
        v2 + (v21 ,v22 ,...,v2n)
        .
        .
        vr = (vr1,vr2,...,vrn)
        and consider the equation
        k1vi _ k2v2 +... + krvr = 0
        if we express both sides of this equation in terms of components and then equate the corresponding components, we obtain the system
        v11k1 + v21k2 + ...+ vr1kr = 0
        v12k1 + v22k2 + ...+ vr2kr = 0
        . . . .
        . . . .
        v1nk1 + v2nk2 + ...+ vrnkr = 0
        This is a homogeneous system of n equations in the r unknowns k1, …, kr. Since r > n, Theorem 1.2.2 implies that the system has nontrivial solutions, so S = {v1, v2, …, vr} is a linearly dependent set.
        
        Linear Independence and Dependence
        If S = {v1, v2, …, vr} is a set of two or more vectors in a vector space V, then S is said to be a linearly independent set if no vector in S can be expressed as a linear combination of the others. A set that is not linearly independent is said to be linearly dependent. If S has only one vector, we will agree that it is linearly independent if and only if that vector is nonzero.
        
        A nonempty set S = {v1, v2, …, vr} in a vector space V is linearly independent if and only if the only coefficients satisfying the vector equation
        
        k1v1 + k2v2 + ... + krvr = 0
        are k1 = 0, k2 = 0, …, kr = 0.
        
        (a) A set with finitely many vectors that contains 0 is linearly dependent.
        (b) A set with exactly two vectors is linearly independent if and only if neither vector is a scalar multiple of the other.
        For any vectors v1, v2, …, vr, the set S = {v1, v2, …, vr, 0} is linearly dependent since the equation
        0v1 + 0v2 + ... + 0vr + 1(0) + 0
        expresses 0 as a linear combination of the vectors in S with coefficients that are not all zero.
        
        Linear Independence of functions
        
        If f1 = f1(x), f2 = f2(x), …, fn = fn(x) are functions that are n − 1 times differentiable on the interval (−∞, ∞), then the determinant
        
        is called the Wronskian of f1, f2, …, fn.
        
        If the functions f1, f2, …, fn have n − 1 continuous derivatives on the interval (−∞, ∞), and if the Wronskian of these functions is not identically zero on (−∞, ∞), then these functions form a linearly independent set of vectors in C^(n-1)(−∞, ∞).