1.2 Reading theorems and proof language

Linear algebra is not only a calculation course. Very quickly, it starts to use the language of definitions, theorems, lemmas, proofs, equivalent conditions, and counterexamples. If that language is read loosely, the formulas may still look familiar, but the mathematical content becomes unstable.

This section is a reading guide for the proof language used throughout MATH1030. It is not a separate logic course. Its purpose is practical: when a later note says that several conditions are equivalent, that a vector is unique, or that a proposed statement is false, you should know exactly what kind of claim is being made and what kind of argument can support it.

Statements, assumptions, and conclusions

Most theorem statements in this course have the same logical shape:

Theorem

The usual theorem shape

Suppose the assumptions $P$ are satisfied. Then the conclusion $Q$ follows.

The assumptions are not being asserted in isolation. The theorem says that whenever the assumptions are true in a particular situation, the conclusion is also true in that situation.

That distinction prevents several common mistakes. The statement

If a square matrix is invertible, then its RREF is the identity matrix.

does not say that every square matrix is invertible. It also does not say that every matrix whose RREF is the identity must be introduced through the same proof. It states a conditional implication from one property to another.

Definition

Conditional statement

A conditional statement has the form "if $P$, then $Q$". The part $P$ is the assumption or hypothesis. The part $Q$ is the conclusion.

When reading a theorem, always separate these two parts before trying to use the result:

1. What objects are being discussed?
2. What assumptions are imposed on those objects?
3. What conclusion is guaranteed?
4. Is the theorem being used in the forward direction, the reverse direction, or as part of an equivalence?

Proof X-Ray

Parse the statement before choosing a proof

Consider the claim: if $u$ and $v$ solve the same system $Ax=b$, then $A(u-v)=0$. First fix the objects: $A$ is an $m\times n$ real matrix, $b\in\mathbb R^m$, and $u,v\in\mathbb R^n$. The hypotheses are the two equalities $Au=b$ and $Av=b$. The conclusion concerns their difference, not either solution separately.

The useful definition turns “solve the same system” into these two equations. Distributivity then gives

$$A(u-v)=Au-Av=b-b=0.$$

Each equality has a reason: the first uses a matrix law, the second uses both hypotheses, and the last is ordinary vector subtraction. We have not assumed that either solution is zero, nor that the system has a unique solution. We have also not assumed that $A$ is square or invertible. None of those stronger hypotheses is needed for the displayed argument.

To read a proof backwards, ask what would break if one hypothesis disappeared. If $Au=b$ and $Av=c$ with different right-hand sides, the same calculation gives $A(u-v)=b-c$, which need not be zero. This identifies exactly where “the same system” enters the reasoning. A proof is more informative when its assumptions can be located in the calculation, rather than merely listed at the beginning.

Read “and” and “or” with their scope

An assertion that a matrix is symmetric and invertible requires both properties; verifying only symmetry is not enough. The mathematical word or is inclusive unless stated otherwise: “$u=0$ or $v=0$” permits both to be zero. When assumptions combine several conditions, brackets say which conditions are grouped. The statement “$A$ is square and either $A$ is singular or $A$ is symmetric” still requires squareness in either case.

The same care applies to conclusions. To prove both conclusions, supply both arguments. To disprove a claim that guarantees both, it is enough to find an object satisfying every assumption but violating one of the required conclusions. Neither task is settled by checking a few unrelated examples.

The converse is a different statement

The converse of "if $P$, then $Q$" is "if $Q$, then $P$". These two statements are not the same. One may be true while the other is false.

Worked example

Do not silently reverse a theorem

The statement

$$\text{if } A \text{ is invertible, then } Ax=0 \text{ has only the zero solution}$$

has converse

$$\text{if } Ax=0 \text{ has only the zero solution, then } A \text{ is invertible}.$$

For a square matrix, both statements are true as part of the invertible-matrix dictionary. But that is extra information supplied by a theorem. You cannot reverse a conditional merely because the forward direction looks plausible.

This is why MATH1030 often presents results as dictionaries:

Theorem

Equivalence format

The following statements are logically equivalent:

1. $P$;
2. $Q$;
3. $R$.

Such a result means that the statements stand or fall together. In practice, you may use any one of them to prove any other. But to prove the dictionary itself, one must establish enough implications to connect all the statements, not merely write them in a list.

Contrapositive and direct proof

The contrapositive of "if $P$, then $Q$" is "if not $Q$, then not $P$". A conditional and its contrapositive are logically equivalent.

In this course, however, many arguments are best written directly. Matrix and vector proofs usually involve equations, and equations are easiest to control when the proof begins from the assumptions and builds toward the conclusion.

Definition

Direct proof

A direct proof starts from the assumptions, uses definitions, earlier theorems, and calculations, and then derives the desired conclusion step by step.

For example, to prove that the null space of a matrix is a subspace, a direct proof begins with vectors in the null space, uses the equations $Au=0$ and $Av=0$, and then checks closure:

$$A(u+v)=Au+Av=0+0=0, \qquad A(cu)=cAu=c0=0.$$

The proof succeeds because the calculations are attached to the exact defining condition.

Definitions are not theorems

A definition introduces a name or a condition. It is not the kind of statement that is true or false, and it is not something to be proved. Once a definition has been introduced, later arguments may use it.

Definition

Definition-reading habit

When reading a definition, identify:

1. the objects to which the definition applies;
2. the name being introduced;
3. the defining condition;
4. any earlier definitions required to understand that condition.

For instance, "a matrix is symmetric if $A^T=A$" gives a criterion. To prove that a particular matrix is symmetric, you compute its transpose and verify the criterion. To use symmetry later, you may replace $A^T$ by $A$ because the definition gives that equality.

Quantifiers and existence claims

Words such as "for every", "for some", "there exists", "at most one", and "unique" carry mathematical content. They are not decorative.

Fix a matrix $A$. The statement “for every $b$, there exists $x$ such that $Ax=b$” permits the chosen solution to depend on the right-hand side. It says that after an arbitrary target has been supplied, a solution can be found. The reversed statement “there exists $x$ such that for every $b$, $Ax=b$” asks for one fixed solution that works for all targets at once. The two statements have different content even though they use the same equation.

For the one-dimensional identity matrix $A=[1]$, the first is true: given any real $b$, choose $x=b$. The second is false: the same number cannot satisfy both $x=0$ and $x=1$. This example isolates the order of choices without any matrix calculation. In a written existence proof, introduce the arbitrary right-hand side first, then construct the solution. Otherwise it may be unclear whether the constructed object is allowed to depend on that right-hand side.

Negation also changes the order-sensitive words. To deny that every target has a solution, one must exhibit a target for which no solution exists. A failed attempt to guess a solution is not enough. To deny that every solution is zero, one must exhibit a nonzero solution and check the defining equation. In either case, the negation tells us both what object to provide and what to verify.

Theorem

Existence and uniqueness split

A statement saying "there exists a unique object with property $P$" has two parts:

1. existence: at least one object with property $P$ exists;
2. uniqueness: at most one object with property $P$ exists.

This split is especially important in linear algebra. When we later say that coordinates relative to an ordered basis are unique, the existence part says that every vector in the space can be expressed using the basis. The uniqueness part says that two different coefficient lists cannot represent the same vector.

Worked example

How an at-most-one proof is usually written

To prove that there is at most one object with a property, do not start by trying to find the object. Instead, suppose two objects have the property and prove that they must be equal.

For example, to prove uniqueness of coordinates, suppose

$$x=a_1b_1+\cdots+a_pb_p \qquad\text{and}\qquad x=c_1b_1+\cdots+c_pb_p.$$

Subtracting gives

$$0=(a_1-c_1)b_1+\cdots+(a_p-c_p)b_p.$$

If $b_1,\ldots,b_p$ are linearly independent, all coefficients must be zero. Hence $a_i=c_i$ for every $i$.

Counterexamples disprove universal claims

Many false statements in mathematics are disproved by a counterexample. The counterexample must satisfy the assumptions but fail the conclusion.

Definition

Counterexample

A counterexample to "if $P$, then $Q$" is a concrete object or situation for which $P$ is true but $Q$ is false.

The preparatory work is often the hard part: you have to guess where a failure may occur. The written argument, however, must be explicit:

1. name the object;
2. verify that it satisfies the assumptions;
3. verify that it fails the conclusion.

Worked example

A linear algebra counterexample

Consider the false statement:

If two $2\times 2$ matrices have the same determinant, then they are equal.

Take

$$A= \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}, \qquad B= \begin{bmatrix} 2 & 0\\ 0 & \frac12 \end{bmatrix}.$$

Both matrices are $2\times 2$, and

$$\det(A)=1,\qquad \det(B)=1.$$

So the assumption is satisfied. But $A\ne B$, so the conclusion fails. This single example disproves the universal claim.

Counterexample mode

A missing hypothesis changes the claim

Consider the proposed rule: whenever the only solution of $Ax=0$ is zero, every system $Ax=b$ is consistent. The square-matrix hypothesis from the invertibility dictionary has been omitted. Test the actual broader claim with

$$A=\begin{bmatrix}1\\0\end{bmatrix},\qquad b=\begin{bmatrix}0\\1\end{bmatrix}.$$

Here the unknown $x$ is a real number. The homogeneous equation is the pair of conditions $x=0$ and $0=0$, so its only solution really is zero. But $Ax=b$ would require $x=0$ and $0=1$ simultaneously. It has no solution. Thus the hypothesis of the proposed rule is satisfied and its conclusion fails.

The example does not contradict the theorem about square matrices: this matrix has two rows and one column. Rather, it shows why removing a dimensional assumption needs justification. Giving a square invertible example where the rule works would not repair the universal claim; one valid failure already disproves it. Likewise, a matrix with a nontrivial homogeneous solution would not be a counterexample here, because it would fail the hypothesis itself. The repaired statement restores the square hypothesis: for a real square matrix, if the homogeneous system has only the zero solution, then every dimensionally compatible right-hand side gives a unique solution. The invertibility theorem later proves this implication.

Existence and uniqueness need separate evidence

An “at most one” proof does not construct an object. The real equation $x^2=-1$ has at most one real solution in the logical sense that no pair of distinct real solutions exists, but it has no real solution at all. To claim exactly one, both existence and at-most-one must be established. Conversely, providing a solution proves existence but says nothing about whether another solution might exist.

When reading the coordinate argument above, separate its two roles. Linear independence proves that two representations cannot have different coefficient lists. A separate spanning assumption is needed to guarantee that a representation exists for the vector under discussion. Later basis theory combines precisely these two requirements. This is an example of a logical split revealing why a mathematical definition contains two conditions.

How this note should affect later reading

The practical reading routine is:

1. mark the assumptions and conclusions in every theorem;
2. avoid reversing implications unless an equivalence theorem allows it;
3. treat definitions as criteria that can be checked and used;
4. split existence from uniqueness;
5. use counterexamples only when the proposed statement is universal and false.

Checkpoint

A theorem says: if $P$, then $Q$. Which statement is automatically equivalent to it?

Compare the converse with the contrapositive before answering.

Solution · Answer

The contrapositive, "if not $Q$, then not $P$", is automatically equivalent to the theorem. The converse, "if $Q$, then $P$", is a different statement and needs its own proof.

Exercises

Exercise 1

A result says:

If the columns of a square matrix $A$ are linearly independent, then $A$ is invertible.

Write the converse of this statement. Does the original statement alone prove the converse?

Solution · Guided solution for exercise 1

The converse is:

If $A$ is invertible, then the columns of $A$ are linearly independent.

The original statement alone does not prove the converse. In MATH1030 the converse is true, but it needs a theorem from the invertible-matrix dictionary, not a silent reversal of the original implication.

Exercise 2

Disprove the statement:

If a real number $x$ satisfies $x^2>0$, then $x>0$.

Solution · Guided solution for exercise 2

Take $x=-1$. Then $x$ is a real number and $x^2=1>0$, so the assumption is satisfied. But $x>0$ is false. Therefore this $x$ is a counterexample, and the statement is false.

Exercise 3: identify what a negation requires

For a fixed real matrix $A$, negate the claim: “For every dimensionally compatible right-hand side $b$, there exists exactly one $x$ satisfying $Ax=b$.” Explain the two ways the claim can fail. Illustrate both with the one-dimensional zero matrix.

Solution · Solution to exercise 3

The negation says that there is at least one dimensionally compatible right-hand side for which the equation does not have exactly one solution. For that right-hand side, either there is no solution, or there are at least two distinct solutions. To make this a complete argument for a particular matrix, one must identify such a right-hand side and verify one of those failures.

Take $A=[0]$. For $b=1$, the equation is $0x=1$, which has no solution. For $b=0$, the equation is $0x=0$, and both $x=0$ and $x=1$ are solutions. Either choice of right-hand side already disproves the original claim. The examples diagnose different failures: the first violates existence, and the second violates uniqueness. We do not need one right-hand side that violates both simultaneously; no solution and multiple solutions are incompatible cases.

Exercise 4: verify a whole equivalence chain

Suppose statements $P,Q,R$ have been shown to satisfy $P\Rightarrow Q$ and $Q\Rightarrow R$. Is that enough to conclude that all three are equivalent? What one additional implication would suffice?

Solution · Solution to exercise 4

No. The two implications give a forward chain, but do not return from $R$ to $P$. Proving $R\Rightarrow P$ closes the cycle. Following the cycle then supplies a route from each statement to each of the other two, which is exactly what equivalence requires. For example, $Q\Rightarrow P$ follows by first using $Q\Rightarrow R$ and then $R\Rightarrow P$. This explains how a long matrix-theorem dictionary can be proved without writing every pair of implications separately, while still proving more than a one-way list.