Matrices 3. Homogeneous and Inhomogeneous Systems

Matrices 3. Homogeneous and Inhomogeneous Systems Theorems about homogeneous and inhomogeneous systems. On the basis of our work so far, we can formulate a few general results about square systems of linear equations. They are the theorems most frequently referred to in the applications. Definition. The linear system Ax = b is called homogeneous if b = 0; otherwise, it is called inhomogeneous. Theorem 1. Let A be an n × n matrix. (20) |A| = 6 0 ⇒ A x = b has the unique solution, x = A−1 b . (21) |A| = 6 0 ⇒ A x = 0 has only the trivial solution, x = 0. Notice that (21) is the special case of (20) where b = 0. Often it is stated and used in the contrapositive form: (21′ ) Ax = 0 has a non-zero solution ⇒ |A| = 0. (The contrapositive of a statement P ⇒ Q is not-Q ⇒ not-P ; the two statements say the same thing.) Theorem 2. Let A be an n × n matrix. (22) (23) |A| = 0 |A| = 0 ⇒ ⇒ A x = 0 has non-trivial (i.e., non-zero) solutions. A x = b usually has no solutions, but has solutions for some b. In (23), we call the system consistent if it has solutions, inconsistent otherwise. This probably seems like a maze of similar-sounding and confusing theorems. Let’s get another perspective on these ideas by seeing how they apply separately to homogeneous and inhomogeneous systems. Homogeneous systems: Ax = 0 has non-trivial solutions ⇔ |A| = 0. Inhomogeneous systems: Ax = b has the unique solution x = A−1 b, if |A| 6= 0. If |A| = 0, then Ax = b usually has no solutions, but does have solutions for some b. The statements (20) and (21) are proved, since we have a formula for the solution, and it is easy to see by multiplying A x = b by A−1 that if x is a solution, it must be of the form x = A−1 b. We prove (22) just for the 3 × 3 case, by interpreting it geometrically. We will give a partial argument for (23), based on both algebra and geometry. Proof of (22). We represent the three rows of A by the row vectors a, b, c and we let x = (x, y, z); think of all these as origin vectors, i.e., place their tails at the origin. Then, considering the homogeneous system first, (24) Ax = 0 is the same as the system 1 a · x = 0, b · x = 0, c · x = 0. 2 HOMOGENEOUS AND INHOMOGENEOUS SYSTEMS In other words, we are looking for a row vector x which is orthogonal to three given vectors, namely the three rows of A. By Section 1, we have |A| = a · b × c = volume of parallelepiped spanned by a, b, c. It follows that if |A| = 0, the parallelepiped has zero volume, and therefore the origin vectors a, b, c lie in a plane. Any non-zero vector x which is orthogonal to this plane will then be orthogonal to a, b, c, and therefore will be a solution to the system (24). This proves (22): if |A| = 0, then A x = 0 has a nontrivial solution. Partial proof of (23). We write the system as A x = d, where d is the column vector d = (d1 , d2 , d3 )T . Writing this out as we did in (24), it becomes the system (25) a · x = d1 , b · x = d2 , c · x = d3 . If |A| = 0, the three origin vectors a, b, c lie in a plane, which means we can write one of them, say c, as a linear combination of a and b: (26) c = ra + sb, r.s real numbers. Then if x is any vector, it follows that (27) c · x = r(a · x) + s(b · x) . Now if x is also a solution to (25), we see from (25) and (27) that (28) d3 = rd1 + sd2 ; this shows that unless the components of d satisfy the relation (28), there cannot be a solution to (25); thus in general there are no solutions. If however, d does satisfy the relation (28), then the last equation in (25) is a conse­ quence of the first two and can be discarded, and we get a system of two equations in three unknowns, which will in general have a non-zero solution, unless they represent two planes which are parallel. Singular matrices; computational difficulties. Because so much depends on whether |A| is zero or not, this property is given a name. We say the square matrix A is singular if |A| = 0, and nonsingular or invertible if |A| = 6 0. Indeed, we know that A−1 exists if and only if |A| 6= 0, which explains the term “invertible”; the use of “singular” will be familiar to Sherlock Holmes fans: it is the 19th century version of “peculiar” or the late 20th century word “special”. Even if A is nonsingular, the solution of Ax = b is likely to run into trouble if |A| ≈ 0, or as one says, A is almost-singular. Namely, in the formula for A−1 the |A| occurs in the denominator, so that unless there is some sort of compensation for this in the numerator, the solutions are likely to be very sensitive to small changes in the coefficients of A, i.e., to the coefficients of the equations. Systems (of any kind) whose solutions behave this way HOMOGENEOUS AND INHOMOGENEOUS SYSTEMS 3 are said to be ill-conditioned; it is difficult to solve such systems numerically and special methods must be used. To see the difficulty geometrically, think of a 2 × 2 system Ax = b as representing a pair of lines; the solution is the point in which they intersect. If |A| ≈ 0, but its entries are not small, then its two rows must be vectors which are almost parallel (since they span a parallelogram of small area). The two lines are therefore almost parallel; their intersection point exists, but its position is highly sensitive to the exact positions of the two lines, i.e., to the values of the coefficients of the system of equations.