Linear Algebra Proof-writing examples

Proof-writing examples Math 272, Fall 2019 The purpose of this document is to provide a couple examples of how to organize and write proofs in this class. There is no single “format” that you must follow; I have aimed to highlight a couple different ways you can organize your work. A few general tips to keep in mind. 1. The first step in writing a proof is to convince yourself that statement is true. Make sure you really believe it! Play devil’s advocate, and look for any possible weakness in your reasoning. 2. You can write either in English or in symbols. If you write in symbols, remember that you should still follow basic grammar. The symbol “=” is a verb; an equation like 5 = x + 2 is a complete sentence. 3. Always explain notation before you use it. Never write ~x until you’ve told me what it is, e.g. by writing “let ~x ∈ R3 be an arbitrary vector.” 4. Begin by clearly stating your assumptions. 5. Every statement you make (after your assumptions) should be supported either by statements you have already proved (or which have been proved in class) or by your assumptions. When in doubt, explicitly cite the fact that supports your claim (e.g. “by Theorem 2 on page 107 of the textbook”). 6. You can always bring a draft proof to me in office hours, and we can talk through it, both in content and style. 1 Converses, and “if and only if ” statements Consider the following proposition1 . Proposition 1. Suppose that A is an invertible n × n matrix, and ~x, ~b are vectors in Rn . Then A~x = ~b if and only if ~x = A−1~b. The phrase “if and only if” here actually means that we are making two statements at once: • If A~x = ~b, then ~x = A−1~b. • If A−1~b = ~x, then A~x = ~b. These statements are closely related, but they are not equivalent. Instead, each one is called the converse of the other. Vocabulary: The converse of a statement “P implies Q” is the statement “Q implies P.” A statement can be true even if its converse is false. The phrase “P if and only if Q” means that both “P implies Q” and “Q implies P” are true. It is common in math to abbreviate the phrase “if and only if” by simply writing “iff.” Here is one way to write a proof of Proposition 1. 1 A “proposition” is simply a statement to be proved. It is essentially interchangeable with the word “theorem,” although traditionally “theorem” is reserved for more important or powerful statements. page 1 of 8 Proof-writing examples Math 272, Fall 2019 Proof of Proposition 1 (“⇒”) Suppose that A~x = ~b. Multiplying both sides by A−1 , it follows that A−1 A~x = A−1~b. Since A−1 A = I and I~x = ~x, this implies that ~x = A−1~b. (“⇐”) Conversely, suppose that x = A−1~b. It follows that A~x = AA−1~b. Since AA−1 = I and I~b = ~b, this implies that A~x = ~b. Therefore A~x = ~b if and only if ~x = A−1~b.  The two symbols “⇒” and “⇐” are just a handy visual cue to the reader, informing her which implication you are proving. They also help you quickly glance over your work to check that you’ve proved both of them. However, they are not strictly necessary. Some observations about this proof: 1. It is really two proofs in one. Each paragraph is a self-contained proof. 2. The word “conversely” signals to the reader that one statement has just been proved (in this case, “if A~x = ~b, then ~x = A−1~b”), and that the author is now setting out the prove the converse (“if ~x = A−1~b, then A~x = ~b”). 3. Each paragraph is a sequence of claims. Each claim in the sequence is supported by the previous claims in the paragraph, or previously proved facts. For example, the first paragraph consists of the following four statements, each of which is justified in a different way: (a) A~x = ~b (the initial assumption) (b) A−1 A~x = A−1~b (justified by the phrase “multiplying both sides by A−1 ”) (c) A−1 A = I (justified by the definition of “inverse”) (d) I~x = ~x (justified by a general fact about identity matrices) (e) ~x = A−1~b (justified by the previous three statements put together) Here is a second way to write essentially the same proof, but relying more on symbols than on words. Notation: The symbol “⇒” means “implies.” The symbol ⇔ means “if and only if.” These symbols can be chained together, as in the following proof. If you prove that P ⇒ Q and Q ⇒ P , then you have proved that P ⇔ Q. page 2 of 8 Proof-writing examples Math 272, Fall 2019 Another proof of Proposition 1 (more symbols, fewer words) First, observe that A~x = ~b ⇒ A−1 A~x = A−1~b ⇒ I~x = A−1~b ⇒ ~x = A−1~b. Conversely, ~x = A−1~b ⇒ A~x = AA−1~b ⇒ A~x = I~b ⇒ A~x = ~b. Therefore A~x = ~b ⇔ ~x = A−1~b. 2  Proving uniqueness The following two propositions are both examples of proving that something is unique. There are two main ways to prove that something is unique: 1. Give an explicit formula for it, and prove that this formula is correct. 2. Begin by assuming that you have two such things. Prove that they are equal to each other. Here’s an example of a proof that proves that something is unique using the first method. Proposition 2. If A is an invertible n×n matrix, and ~b is a vector in Rn , then the matrix equation A~x = ~b always has a unique solution ~x. Proof of Proposition 2 Existence: Proposition 1 implies that A−1~b is a solution. Uniqueness: Proposition 1 implies that if ~x is a solution, then ~x = A−1~b. So no other solution exists.  Comments: 1. Proposition 2 makes two claims: that a solution exists, and that it is unique. That is why the proof is separated into two parts, which are labeled to aid the reader. 2. Because we recently proved a proposition that is very useful (Proposition 1), it was convenient to simply cite it and use its conclusions. There is no need to reinvent the wheel. Here’s another statement, with the second sort of uniqueness proof. Proposition 3. Suppose that A is a square matrix. If A is invertible, then the inverse matrix is unique. page 3 of 8 Proof-writing examples Math 272, Fall 2019 Proof of Proposition 3 Suppose that B1 and B2 are both inverses of A. Then both B1 A and B2 A are equal to the identity matrix I. In particular, they are equal to each other: B1 A = B2 A. Therefore, multiplying both sides of this equation by B2 on the right, and using the fact that B2 is an inverse, we obtain the following equations. B1 AB2 = B2 AB2 ⇔ B1 (AB2 ) = B2 (AB2 ) ⇔ B1 I = B2 I ⇔ B1 = B2 (All the equations above are equivalent, since each rewrites the previous one in a different way, using associativity and the definition of identities and inverses.) Hence any two inverses of A must in fact be equal to each other.  Observe that, read literally, this proof demonstrated this statement: “If B1 is an inverse of A, and B2 is an inverse of A, then B1 = B2 .” The point is that this is just a cumbersome way to say what we actually care about: “the inverse of A is unique.” 3 The contrapositive I mentioned earlier that the converse of a statement is not equivalent to the statement. However, there is another variation that is equivalent to the original statement. Vocabulary: The contrapositive of a statement “P implies Q” is the statement “If Q is false, then P is false.” Key fact: A statement is true if and only if its contrapositive is true. For example, first consider the following statement, which follows quickly from an earlier proposition. Proposition 4. If A is invertible, then the only solution ~x to the matrix equation A~x = ~0 is the trivial solution ~x = ~0. Proof of Proposition 4 It follows from Proposition 1 that the only solution to A~x = ~b is ~x = A−1~0 = ~0.  Once we know this proposition, we can use its contrapositive to deduce the follow corollary2 . Corollary 5. If A is a matrix, and there exists a nonzero vector ~v such that A~v = ~0, then A is not invertible. 2 The word “corollary,” like “proposition,” just means a statement to be proved. It is usually reserved for statements that can be easily deduced from a previously proved statement. page 4 of 8 Proof-writing examples Math 272, Fall 2019 Proof of Corollary 5 Suppose that A~v = ~0. Proposition 4 says that if A is invertible, then ~v = ~0. By the contrapositive, if ~v 6= ~0, then A is not invertible, as desired.  4 Equality of sets It is frequently convenient to express certain if and only if statements as equation of sets. For example, consider the following proposition. Proposition 6. Let A be an m × n matrix, and ~b ∈ Rm a vector. Suppose that the matrix equation A~x = ~b has at least one specific solution, ~x = ~v (that is, ~v ∈ Rn satisfies A~v = ~b). Then the set of all solutions to A~x = ~b can be described in terms of the set of solutions to a homogeneous matrix equation, as follows. n o n o ~x ∈ Rn : A~x = ~b = ~v + w ~: w ~ ∈ Rn and Aw ~ = ~0 Comment 1: The curly bracket notation above is called “set builder notation.” If you’ve never seen it before, don’t worry! n With a bit ofopractice you’ll become fluent with it. Here’s how you read it: the expression ~x ∈ Rn : A~x = ~b would be read, in English, as “the set of all vectors ~x in Rn satisfying the equation A~x = ~b.” The text on the left of the colon gives a formula for the elements in the set, while the text on the right of the colon specifies the criteria that must be met in order to include this in the set. The formula on the right means: find all the choices of w ~ solving the homogeneous equation, and add each one to ~v ; bundle all those sums together into a set. Comment 2: It can be dizzying to keep the many variables in this statement straight, so take your time reading it! It may help to repeat to yourself a brief description of each variable when you read it, as in “~v , the specific solution to the inhomogeneous equation, plus w, ~ a solution to the homogeneous equation.” The more you practice using the terms in complete sentences, the easier a time you’ll have keeping straight which one is which. There are many ways to prove that two sets are equal, but one of the most reliable and common in a course like this is a “double-containment proof.” In this type of proof, you show two claims: first, assume you have an element of the set on the left. Prove that it is also an element of the set on the right. This proves that the left set is contained in the right set. Next, assume that you have an element of the set on the right. Prove that it is an element of the set on the left. This shows that reverse containment. Together, these two containments mean that the sets are equal. For example, here’s a double-containment proof of Proposition 6. page 5 of 8 Proof-writing examples Math 272, Fall 2019 Proof of Proposition 6 n o (“⊆”) Suppose that ~x ∈ ~x ∈ Rn : A~x = ~b . Then A~x = ~b and also A~v = ~b (since we are assuming that ~v is a specific solution). Therefore by distributivity, A(~x − ~v ) = A~x − A~v = ~b − ~b = ~0. Let w ~ = ~x − ~b. Then we have shown that Aw ~ = ~0, so n o n ~ ~x = ~v + w ~ ∈ ~v + w ~: w ~ ∈ R and Aw ~ =0 . n o (“⊇”) Suppose that ~x ∈ ~v + w ~: w ~ ∈ Rn and Aw ~ = ~0 . Then there exists w ~ ∈ Rn such that Aw ~ = ~0 and ~x = ~v + w. ~ It follows that A~x = A(~v + w) ~ = A~v + Aw ~ = ~b + ~0 = ~b, n o hence ~x ∈ ~x ∈ Rn : A~x = ~b , as desired.  The symbols ⊆, ⊇ mean “is a subset of” and “contains as a subset,” respectively. Including them at the beginning of the two parts of the proof is optional, but can be a helpful visual cue to the reader. Double-containment proofs can be understood as a specialized type of “if and only if” proof. You’re proving that “for all x, x is in the left set if and only if x is in the right set.” The two containments are merely one implication and its converse. 5 Casework Sometimes in a proof, you will desperately want to make some simplifying assumption, but cannot because it is not necessarily true. For example, suppose we wish the prove the following statement (mentioned in class earlier).   a b Proposition 7. Suppose that A = is a 2 × 2 matrix, and ad − bc = 0. Then A is not c d invertible. Here is a first attempt at a proof, which unfortunately contains a flaw. Flawed proof of Proposition 7       d ad − bc 0 Let ~v = . Then A~v = = . By Corollary 5, A is not invertible. −c cd − dc 0  Before reading on, try to identify the flaw in this proof. page 6 of 8 Proof-writing examples Math 272, Fall 2019 ~ The flaw in the proof is this: in order to apply Corollary   5, we need to assume that ~v 6= 0. But 1 0 this might not be right! For example, A could be . This matrix has ad − bc = 0, and the 1 0 statement we want to prove is true (it isn’t invertible), but our proof doesn’t work. We need a different proof for matrices like this one. The key technique for situations like this is to do some casework. If you would love to make a simplifying assumption (in this case, the assumption that ~v = ~0), do it. The catch is that afterwards, you should make the opposite assumption, and prove that the statement you want is still true in that case. More generally, you can break your work up into several distinct cases, each with a different assumption, and prove the statement in each case separately. As long as you can be sure that at least one case holds in every situation, you will have a complete proof. Here’s an example, showing how to fix the flaw in the first proof attempt by working two separate cases. Corrected proof of Proposition 7       0 ad − bc d . = . Observe that A~v = Let ~v = 0 cd − dc −c Case 1: ~v 6= ~0. In this case, ~v constitutes a nonzero solution to the matrix equation A~x = ~0. By Corollary 5, this implies that A is not invertible.   a b ~ Case 2: ~v = 0. In this case, it follows that both d and c are equal to 0, so A = , 0 0   0 has no i.e. the second row of A is zero. But in this case, the matrix equation A~x = 1 solution, since multiplying A by any vector will always give 0 in the second coordinate. But Proposition 2 asserts that if A is invertible, then every equation A~x = ~b must have a solution. By the contrapositive, it follows that A is not invertible.  If you have done any computer programming, this kind of casework should remind you of checking edge cases. In both cases, you first do the work of writing a proof (or writing some code) that works in a typical situation, and then you stop and think about any non-typical situations where the logic breaks down. page 7 of 8 Proof-writing examples 6 Math 272, Fall 2019 Proof by contradiction Closely related to the concept of contrapositive statements is the technique of “proof by contradiction.” It works like this: if you want to prove P, you can begin by assuming that P is false, and then deduce something absurd (a contradiction). This contradiction will show that it was impossible for P to be false after all, i.e. that P must be true. As an example, here’s another proof of Corollary 5. Another proof of Corollary 5, by contradiction Suppose that A is a matrix and ~v is a nonzero vector such that A~v = ~0. Assume, for the sake of contradiction, that A is invertible. Then multiplying both sides by A−1 yields ~v = A−1~0. The zero vector gives ~0 when multiplied by any matrix, so ~v = ~0. This is a contradiction, since we assumed that ~v is nonzero . Therefore our assumption cannot be true: A is not invertible.  The symbols and are optional (and idiosyncratic), but I like them. They are visual cues to label the place where you may an assumption to be contradicted, and the place where you obtain a contradiction. Together, they make it easy to see the logical outline of the proof, and also to quickly identify what it is that is proved once you get your contradiction. As a final example, involving both some casework and a proof by contradiction, I will give a proof of the following fact that I stated without proof in class. Proposition 8. If A is a nonsquare matrix, then A is not invertible. The key to the proof I write below is to recognize that nonsquare matrices come in two flavors: either they have more columns than rows, or they have more rows than columns. It turns out that these two cases fail to be invertible for different reasons. Proof of Proposition 8 Let m, n the number of rows and columns in A, respectively. So A is an m × n matrix. Case 1: m < n. In this case, A has more columns than rows. The equation A~x = ~0 can be solved by setting up an augmented matrix with A on the left of the partition, and all 0’s on the right. After row-reducing this matrix, there is at most one pivot in each of the m rows. Since m < n, this means that there is at least one column among the first n columns that does not have a pivot in it. This means that there is at least one free variable in the general solution of A~x = ~b. By selecting this free variable to be nonzero, we obtain a nonzero solution to A~x = ~0. By Corollary 5, it follows that A is not invertible. Case 2: m > n. Assume for the sake of contradiction that A is invertible. Since A−1 A must be an identity matrix, which is a square matrix, it follows that A−1 is an n × m matrix. So A−1 has more columns than rows. By the proof in Case 1, A−1 is not invertible. This is a contradiction, because A is the inverse matrix of A−1 . So our assumption must be false: A is not invertible after all.  page 8 of 8