Proof Techniques in Linear Algebra

Q: How do I decide between a direct proof and its contrapositive?

Compare the two hypotheses. A direct proof starts from $P$; a contrapositive proof starts from $\neg Q$. Whichever gives more concrete material to work with is usually the easier route. Negative conclusions such as the set is not independent often become positive hypotheses under contraposition, which is exactly when the technique pays.

Overview

A theorem is a shortcut. It is proved once, in general, and thereafter can be applied to every particular situation that satisfies its hypothesis without redoing the work. Reading a theorem well therefore means separating it cleanly into two parts — what is assumed and what is concluded — and the most reliable way to do that is to rewrite any statement in the form if something holds, then something else holds. Once a statement is in that form, its hypothesis, its conclusion, its contrapositive and its converse are all visible at a glance.

A definition is a different object and behaves differently. It is a name given to a condition, and it is always a two-way street: a matrix is nonsingular exactly when its homogeneous system has only the trivial solution, so the term may be replaced by the condition and the condition by the term at any point in an argument. Most stalled proofs in linear algebra are unstalled simply by expanding every defined term in the hypothesis and in the conclusion until only primitive statements about vectors and scalars remain.

The catalogue of techniques is short. Set equality is proved by double inclusion. An if and only if statement is proved as two separate implications. An implication that resists direct attack is often easier as its contrapositive. Uniqueness is proved by assuming two candidates and forcing them to coincide. An identity is proved as a chain of equalities, each step justified. A list of equivalent conditions is proved as a cycle of implications rather than every pair. Each pattern is selected by the shape of the conclusion, not by the subject matter.

Two habits matter as much as the patterns. The first is precision of language: eliminating pronouns and vague nouns forces the writer to name the object under discussion, and naming it usually reveals which definitions apply. The second is directionality: exploration may run backwards from the conclusion, but the written proof must run forwards from the hypothesis, because a sequence of manipulations that reaches a true statement proves nothing unless every step is reversible.

Definition

Definition as a Two-Way Implication

PT-D

A definition introduces a term as an exact synonym for a condition. Although usually written as if the condition holds, then the object is called X, it always carries the converse as well: an object called X necessarily satisfies the condition. Definitions may therefore be substituted in both directions without justification.

This is the property that distinguishes a definition from a theorem. Assuming the converse of a theorem is a logical error; assuming the converse of a definition is simply using it.

Theorem, Hypothesis and Conclusion

PT-T

A theorem is a proved statement that can be written as $P \Rightarrow Q$ . The statement $P$ is the hypothesis and $Q$ is the conclusion. To apply a theorem is to verify $P$ in a particular case and immediately assert $Q$ . To prove a theorem is to assume $P$ and derive $Q$ by valid steps.

Every hypothesis is load-bearing until shown otherwise. A theorem quoted without checking its hypothesis is the most common source of confidently wrong conclusions in applied work.

Equivalence (Characterisation)

PT-E

A statement of the form $P \iff Q$ , read P if and only if Q, asserts two implications simultaneously: $P \Rightarrow Q$ and $Q \Rightarrow P$ . Proving it requires both halves, conventionally marked $(\Rightarrow)$ and $(\Leftarrow)$ .

Equivalences are the most useful theorems in the subject because they license substitution in both directions. Where $P$ is expensive to test and $Q$ is cheap, an equivalence is a computational shortcut as well as a structural insight.

Contrapositive and Converse

PT-CP

The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$ ; it is logically equivalent to the original and may be proved in its place. The converse is $Q \Rightarrow P$ ; it is a different statement with no guaranteed relationship to the original.

Negating a compound statement reverses the connective: the negation of A and B is not A or not B. Getting this wrong produces a contrapositive that proves something else entirely.

Concepts

Set equality by double inclusion

Many conclusions in linear algebra are equalities of sets: two systems have the same solution set, a null space equals the trivial subspace, a span equals a column space. The standard method is to prove $S \subseteq T$ and $T \subseteq S$ separately, and each inclusion is itself an implication: assume an arbitrary $x \in S$ and derive $x \in T$ . Two features make this reliable. The element is arbitrary, so nothing may be assumed about it beyond membership; and the two halves are genuinely separate arguments, often of very different difficulty. Omitting the easier half because it seems obvious is the single most common gap in student proofs, and occasionally the easy half is the one that is false.

Proving an identity as a justified chain

To prove $X = Y$ , begin at $X$ and produce a sequence $X = X_1 = X_2 = \cdots = Y$ , annotating each step with the definition, theorem or hypothesis that licenses it. The alternative — writing $X = Y$ and manipulating both sides until something obviously true appears — is unsound, because the manipulations need not be reversible. Squaring both sides of $3 = -3$ reaches the true statement $9 = 9$ without establishing anything. The justified chain also has a practical benefit: when a proof is wrong, the annotation identifies which step failed.

Uniqueness by assuming two

A claim that some object is unique cannot be verified by exhibiting one; it requires ruling out a second. The pattern is to assume two objects $B$ and $C$ both have the stated property and derive $B = C$ . In linear algebra the derivation is usually a short chain: for the inverse of a matrix, $B = BI = B(AC) = (BA)C = IC = C$ . The same pattern establishes uniqueness of the reduced row-echelon form, of a vector's coordinates relative to a basis, and of the solution to a nonsingular system, and in each case the identity element or defining property of the structure does the work.

Cycles for lists of equivalent conditions

A theorem of the form the following are equivalent lists $k$ conditions and asserts that any two are interchangeable, which is $k(k-1)/2$ separate equivalences. Proving them individually would be absurd. Instead the implications are arranged in a cycle, $A_1 \Rightarrow A_2 \Rightarrow \cdots \Rightarrow A_k \Rightarrow A_1$ , so that any condition can be reached from any other by travelling around the ring. Only $k$ implications are proved, and the choice of ordering is a genuine design decision: a good ordering makes each individual implication easy.

Constructive proofs carry algorithms

Existence can be established either by building the object or by arguing that it must exist without producing it. A constructive proof does the former, and its procedure is directly implementable: the proof that every matrix is row-equivalent to one in reduced row-echelon form is the elimination algorithm, and the proof that a spanning set can be reduced to a basis is the casting-out procedure. Where a constructive proof is available it is worth more than the statement it proves. Non-constructive existence results are still valuable, but they do not tell an engineer how to obtain the object.

Decomposition as a proof strategy

Much of school algebra is about simplification — collecting terms, cancelling, factoring. Linear algebra frequently runs the other way, deliberately writing one object as a combination of several: a vector as a linear combination of basis vectors, a solution as a particular solution plus a homogeneous one, a matrix as a product of factors. Expressing something in a more complicated form exposes structure that the compact form hides. Recognising that a conclusion is a decomposition claim, and that the proof will therefore consist of building the pieces and verifying that they recombine, resolves a large fraction of otherwise opaque theorem statements.

Language discipline and object types

Pronouns and the word thing are the enemies of a clear proof. Replacing them forces the writer to name the object, and naming it forces a decision about its type — a scalar, a vector, a set, a subspace, a transformation. Type discipline eliminates whole classes of error before they are written: an expression adding a matrix to a scalar, or comparing a set with a vector, is rejected on sight. This is the same habit that a compiler enforces in typed programming languages, applied to prose.

Selecting a technique from the shape of the conclusion

Rewrite the statement as if-thenSeparate hypothesis from conclusion. Until this is done, no technique can be chosen and the hypotheses cannot be checked.

Expand every defined termReplace each named condition by its definition, in both the hypothesis and the conclusion, until only primitive statements remain.

Is the conclusion an equality of sets?Prove both inclusions separately, each by taking an arbitrary element of one set and deriving membership in the other.

Is the conclusion an if-and-only-if?Split into two implications and prove each independently. Mark which direction is being argued at the start of each half.

Is the conclusion an equality of objects?Build a chain of equalities from one side to the other, annotating every step. Never start by writing the equation to be proved.

Is the conclusion a uniqueness claim?Assume two objects with the property and force them to be equal, rather than exhibiting one and stopping.

Is the direct implication resisting?Try the contrapositive: negate the conclusion, negate the hypothesis, and prove the reversed implication. Negate compound statements carefully.

Equations

Canonical form of a theorem

EQ-PT-01

P \Rightarrow Q

Every theorem can be rewritten in this shape. $P$ is the hypothesis, assumed true; $Q$ is the conclusion, to be derived.

Contrapositive is equivalent; converse is not

EQ-PT-02

(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P), (P \Rightarrow Q) \neq (Q \Rightarrow P)

The first is a tautology and licenses proving the contrapositive instead. The second is a warning: a proved implication says nothing about its converse.

Structure of an equivalence proof

EQ-PT-03

(P \Leftrightarrow Q) \equiv (P \Rightarrow Q) and (Q \Rightarrow P)

Two proofs are required. Each may be attacked directly or through its own contrapositive, and they are frequently of very different difficulty.

Set equality by double inclusion

EQ-PT-04

S = T \Leftrightarrow (S \subseteq T and T \subseteq S), S \subseteq T \Leftrightarrow (x \in S \Rightarrow x \in T)

Both inclusions are needed. Each reduces to an implication about an arbitrary element, which is why set equality proofs look like ordinary implication proofs.

Cycle for multiple equivalences

EQ-PT-05

A_{1} \Rightarrow A_{2} \Rightarrow \dots \Rightarrow A_{k} \Rightarrow A_{1}, (\binom{k}{2}) = \frac{k (k - 1)}{2}

A cycle of $k$ implications yields all $k(k-1)/2$ pairwise equivalences. For a list of six conditions that is six proofs instead of fifteen.

Justified chain of equalities

EQ-PT-06

X = X_{1} = X_{2} = \dots = X_{m} = Y

Each equality is annotated with the definition, theorem or hypothesis that permits it. Begin at $X$ ; never begin by asserting $X = Y$ .

Uniqueness of a matrix inverse

EQ-PT-07

B = B I_{n} = B (A C) = (B A) C = I_{n} C = C

The archetypal uniqueness argument: assume $B$ and $C$ are both inverses of $A$ , then use associativity and the identity to force them to coincide.

Negation of a compound statement

EQ-PT-08

\neg (A and B) \Leftrightarrow (\neg A or \neg B)

Required whenever a contrapositive is formed from a conclusion with more than one clause. Reversing the connective is the step most often forgotten.

Variable Definitions

Symbols used on this page
Symbol	Name	Meaning	Domain / type
$P$	Hypothesis	The statement assumed true at the start of a proof	logical statement
$Q$	Conclusion	The statement to be derived; its shape selects the technique	logical statement
$\Rightarrow$	Implication	If the left statement holds then the right statement holds	logical connective
$\Leftrightarrow$	Equivalence	Implication in both directions; two proofs required	logical connective
$\neg$	Negation	Logical opposite; reverses and and or when applied to a compound	logical operator
$S$	Set	A collection of objects, typically a solution set or a subspace	set
$\subseteq$	Subset	Every element of the left set is an element of the right set	relation on sets
$k$	Condition count	Number of statements in a list of equivalent conditions	positive integer
$N (A)$	Null space	Solution set of the homogeneous system, the subject of the worked proof	subspace of C^n

Worked Numerical Example

Problem statement

Prove the following characterisation, which is used constantly and whose proof exercises four separate techniques: for an $m \times n$ matrix $A$ , the columns of $A$ form a linearly independent set if and only if $\mathcal{N}(A) = \{ \vec{0} \}$ .

Identify the shape of the statement
The phrase if and only if signals an equivalence, so two implications must be proved. Write out both explicitly before starting, and note that the conclusion of one half is an equality of sets, which will require its own double-inclusion argument.
$P : {A_{1}, A_{2}, \dots, A_{n}} independent, Q : N (A) = {\vec{0}}$
Expand every definition
The null space is the set of $\vec{x} \in \mathbb{C}^n$ with $A\vec{x} = \vec{0}$ . The matrix-vector product is the linear combination of the columns whose coefficients are the entries of $\vec{x}$ . Independence means the only coefficients giving the zero vector are all zero. After expansion the two statements are visibly about the same equation.
$A \vec{x} = [\vec{x}]_{1} A_{1} + [\vec{x}]_{2} A_{2} + \dots + [\vec{x}]_{n} A_{n}$
Forward half: assume independence
Take an arbitrary $\vec{x} \in \mathcal{N}(A)$ . Then the displayed combination equals $\vec{0}$ , so it is a relation of linear dependence on the columns. Independence forces every coefficient to be zero, that is $[\vec{x}]_k = 0$ for each $k$ , so $\vec{x} = \vec{0}$ . This establishes one inclusion.
$N (A) \subseteq {\vec{0}}$
Forward half: do not skip the reverse inclusion
The claim is set equality, so the containment in the other direction must also be stated. It holds for every matrix without any hypothesis, since $A\vec{0}$ is a combination with all coefficients zero. Brief as it is, omitting it leaves the equality unproved.
$A \vec{0} = \vec{0} \Rightarrow {\vec{0}} \subseteq N (A)$
Reverse half: assume the null space is trivial
Let $\alpha_1 A_1 + \cdots + \alpha_n A_n = \vec{0}$ be an arbitrary relation of linear dependence on the columns. Assemble the coefficients into the vector $\vec{x}$ with $[\vec{x}]_k = \alpha_k$ . By the expansion in step two, $A\vec{x} = \vec{0}$ , so $\vec{x} \in \mathcal{N}(A)$ .
$\vec{x} \in N (A) = {\vec{0}} \Rightarrow \vec{x} = \vec{0}$
Reverse half: conclude independence
Since $\vec{x} = \vec{0}$ , every $\alpha_k$ is zero. The relation chosen was arbitrary, so the only relation of linear dependence available is the trivial one, which is precisely the definition of an independent set. Both halves are now complete and the equivalence is proved.
$α_{1} = α_{2} = \dots = α_{n} = 0$
Record the contrapositive form for later use
Because the statement is an equivalence, its negation is also an equivalence and may be used freely: the columns are dependent exactly when the null space contains a non-zero vector. Note that this is legitimate only because both directions were proved; the same move applied to a one-way implication would be the converse error.
${A_{1}, \dots, A_{n}} dependent \Leftrightarrow N (A) \neq {\vec{0}}$
Note what the result buys
One side of the equivalence is a statement about infinitely many possible coefficient choices; the other is a single homogeneous system whose solution set is computed by row reduction. The characterisation converts an unbounded search into a finite calculation, which is what makes equivalences the most valuable theorems in the subject.
${A_{1}, \dots, A_{n}} independent \Leftrightarrow rank (A) = n$

Result

The proof required an equivalence split into two halves, a set equality proved by double inclusion within the first half, careful use of an arbitrary element in each direction, and explicit expansion of three definitions before any reasoning began. No step used any property of the entries of $A$ , so the result holds over any field of scalars. The pay-off is a decision procedure: independence of a set of vectors is settled by row-reducing the matrix they form and comparing the rank with the number of columns.

Applications & Industry Use

Software engineering and formal verification

Proof obligations and specification contracts

A function contract states a precondition and a postcondition, which is exactly the hypothesis-and-conclusion structure of a theorem. Verification tools discharge the implication for every reachable state. The same discipline applies informally: a routine documented with a precondition that callers do not check is a theorem applied without verifying its hypothesis, and the failure mode is identical.

Functional safety engineering

Assurance cases and necessary versus sufficient conditions

A safety argument is a structured chain of claims, each supported by evidence, and its weakest points are usually places where a necessary condition has been treated as sufficient — the converse error in a different vocabulary. Writing each claim as an explicit implication, and asking separately whether the converse has been established, exposes those gaps during review rather than during an incident.

Requirements engineering

Acceptance criteria as equivalences

A requirement expressed as the system shall reject an input when condition C holds constrains only one direction; whether the system may also reject inputs when C fails is left open. Stating acceptance criteria as explicit equivalences where equivalence is intended, and as one-way implications where it is not, removes a large class of disputes between supplier and acquirer at no cost.

Control systems engineering

Lists of equivalent characterisations

Controllability, observability and stabilisability each come with several apparently different tests — a rank condition, a reachability condition, a spectral condition. These are presented as lists of equivalent statements, proved as a cycle rather than pairwise, so an engineer may verify whichever member of the list is cheapest for the model at hand and conclude all the others.

Numerical software development

Constructive existence proofs as reference algorithms

Where a proof of existence proceeds by construction, the construction is a specification for an implementation and the proof is a specification for its test suite. Elimination to echelon form, orthogonalisation of a basis and extraction of a basis from a spanning set all enter numerical libraries in this way, with the proof's loop invariants becoming the assertions in the code.

Coding theory and cryptography

Uniqueness arguments and counterexample search

Unique decodability of a code, and the impossibility of a second preimage, are uniqueness claims proved by assuming two candidates and forcing a contradiction. Conversely, refuting a proposed property requires only a single counterexample, which is why attack literature is dominated by explicit constructions rather than general arguments.

Design Considerations

Let the conclusion choose the technique

The subject matter of a statement rarely determines how to prove it; the grammatical shape of its conclusion almost always does. An equality of sets calls for double inclusion, an if and only if for two halves, a uniqueness claim for two assumed objects, an identity for a justified chain. Classify the conclusion before writing anything, and the remaining work is mechanical far more often than it appears.

Explore backwards, write forwards

Working from the conclusion towards the hypothesis is a legitimate and productive way to find a proof, but the finished argument must run in the other direction. Every step written down must be a consequence of what precedes it. A written proof that begins by asserting the conclusion and manipulates it is unsound whenever any step fails to be reversible, and reversibility is easy to lose without noticing.

Never assume the converse of a theorem

A proved implication licenses nothing about its converse. If the converse looks plausible, either prove it separately or hunt for a counterexample; a well-chosen small example settles the question in minutes. Definitions are the exception, since they are equivalences by construction, and keeping definitions and theorems clearly distinguished is what makes the exception safe.

State and honour every hypothesis

Hypotheses such as square, nonsingular, non-zero or consistent are not decoration. When a result is applied, each one must be verified for the case at hand, and when a result is proved, the point at which each hypothesis is used should be identifiable. A hypothesis that is never used is a signal either of a stronger theorem or of an error.

Test a conjecture computationally before proving it

A few minutes with exact arithmetic on small random examples will refute most false conjectures, and the refuting example usually shows which hypothesis is missing. This is not a substitute for proof, and passing a hundred numerical tests establishes nothing, but it is a cheap filter that prevents effort being spent on statements that are simply untrue.

Write with named objects, not pronouns

Replacing it, that and thing with the name of the object forces a decision about what kind of object it is. Type mismatches then become visible in the prose: adding a scalar to a matrix, or comparing a subspace with a vector, is caught while writing rather than during review. The habit costs nothing and improves both the writing and the underlying reasoning.

Standards & Codes

Notation, interchange and numerical standards that govern how this material is written down, stored and computed in production systems.

Applicable standards, conventions and reference implementations
Reference	Title	Relevance to this topic
`ISO 80000-2`	Quantities and units — Part 2: Mathematics	Standardises the logical and set-theoretic symbols used throughout this page — implication, equivalence, negation, membership, inclusion and the quantifiers — so that a written argument is unambiguous across languages and disciplines.
`ISO/IEC/IEEE 29148`	Systems and software engineering — Requirements engineering	Requires that each requirement be singular, verifiable and unambiguous, which in practice means writing it as a clean implication with an identifiable condition and an identifiable obligation.
`ISO/IEC 13568`	Information technology — Z formal specification notation	Standardises a formal notation in which specifications are written as predicates and refinement obligations are discharged as proofs, making the patterns on this page machine-checkable rather than merely conventional.
`IEC 61508`	Functional safety of electrical / electronic / programmable electronic safety-related systems	Recommends formal methods with increasing strength at higher safety integrity levels, so that the distinction between an argued and a proved claim becomes a certification requirement rather than a stylistic preference.
`ISO/IEC 40314`	Mathematical Markup Language (MathML) Version 3.0	Encodes logical connectives semantically rather than as glyphs, so that assistive technology announces an implication as an implication and the direction of an argument survives non-visual reading.

Material Selection

For a mathematical topic, "material" is the numeric representation: the scalar field, storage format and precision the computation is built from.

Representation and precision selection
Representation	Select when	Trade-off
Prose proof with annotated steps	Communication to a human reader; the default for engineering documentation and design justification.	Readable and reviewable at speed, but gaps can hide in phrases such as clearly or similarly, and no mechanical check exists.
Two-column justified chain	Identity proofs and algebraic manipulations, where each step depends on a specific named result.	Makes every justification explicit and localises errors immediately, at the cost of verbosity and a format that reads poorly in continuous prose.
Mechanised proof in a proof assistant	Safety-critical or security-critical claims, or results that will be relied on by many other results.	Gives machine-checked certainty and eliminates hidden gaps, but costs one to two orders of magnitude more effort and requires specialist skill.
Exact rational or integer arithmetic for verification	Checking a specific numerical claim, or testing a conjecture on small cases before attempting a proof.	Settles a particular instance with certainty and refutes false conjectures cheaply; establishes nothing general, however many cases pass.
Modular arithmetic certificates	Confirming a rank, a determinant or a matrix identity on large integer data.	Fast and exact with no coefficient growth, but a result can hold modulo an unlucky prime while failing over the rationals, so several primes are needed.
Floating-point spot check	Rapid plausibility screening only, during exploration.	Immediate and effortless, but rounding makes an exact equality untestable and a rank determination tolerance-dependent; never admissible as evidence in a written argument.

Manufacturing Notes

Implementation notes — how the result is actually produced by hand, by algorithm and by library, including cost and numerical behaviour.

A practical order of operations for writing a proof

Write the hypothesis at the top of the page and the conclusion at the bottom. Expand every defined term in both. Work downwards from the hypothesis and upwards from the conclusion until the two meet. Then rewrite the whole argument cleanly in the forward direction. The rewrite is not optional: the exploratory version almost always contains steps that are reversible in the writer's head but not on the page.

Cost of the cycle strategy for equivalences

Proving $k$ conditions pairwise equivalent by brute force requires $k(k-1)$ implications; a cycle requires $k$ . For the six-condition characterisations of nonsingular matrices that recur throughout the subject, that is six implications instead of thirty. The saving is not merely economy: each implication in a well-ordered cycle is chosen to be individually short, whereas an arbitrary pair may be very hard to connect directly.

Where computation belongs in an argument

Computer algebra is legitimate for verifying a step that is a finite identity in fixed dimensions, for generating candidate counterexamples, and for confirming that a claimed construction produces the stated object. It is not legitimate as a substitute for a general argument, and a result checked on a thousand random matrices remains a conjecture. Keep the two roles clearly labelled in any document that mixes them.

Recognising a proof that will become an algorithm

If a proof of existence contains a loop, a recursion or a repeated selection, it is constructive and can be transcribed into code almost directly. The invariant maintained by the proof becomes the assertion in the implementation, and the termination argument becomes the loop bound. Reading such proofs with implementation in mind extracts two deliverables from one piece of work.

Reviewing someone else's proof

Three checks catch most defects. Confirm that every hypothesis is used somewhere, or explain why not. Confirm that both halves of every equivalence and both inclusions of every set equality are present. Confirm that no step relies on the converse of a cited result. Applying these mechanically is faster than reading for comprehension and finds a different, largely complementary, set of errors.

Failure Modes & Common Mistakes

Failure modes, root causes and prevention
Failure mode / mistake	Impact	Root cause	Prevention & detection
Using the converse of a theorem	high	Treating a proved implication as if it ran both ways, typically because the converse sounds equally reasonable.	Check whether the result was stated as an implication or an equivalence. If the converse is needed, prove it separately or find a counterexample.
Proving only one inclusion of a set equality	high	Stopping after the harder direction because the other seems too obvious to write.	State both inclusions explicitly, however short. Occasionally the direction that looks obvious is the one that fails.
Starting from the conclusion	high	Writing the equation to be proved and manipulating both sides until a true statement appears.	Explore in that direction if it helps, but write the final argument forwards from the hypothesis, with every step a consequence of what precedes it.
Silently dropping a hypothesis	high	Applying a result to a matrix that is not square, not nonsingular or not consistent, because the hypothesis was not re-read at the point of use.	List the hypotheses at the point of application and tick each one against the case at hand. A hypothesis never used in a proof is itself a warning sign.
Mis-negating a compound statement	medium	Forming a contrapositive from a conclusion with two clauses and keeping and where or is required.	Apply the negation rule explicitly and write the negated statement out in full before using it. Check it against a small concrete instance.
Proof by example	high	Verifying a general claim on one or several particular matrices and treating the claim as established.	An example can refute a universal claim but never prove one. Examples belong in the exploration phase and in the exposition, not in the argument.
Circular reasoning through a chain of results	medium	Invoking a theorem whose own proof depends, directly or at a distance, on the statement being proved.	Track the dependency order of the results being used. In a long development this is easiest to check by noting which results precede which.
Ignoring a degenerate case	medium	Arguing about an arbitrary element without considering that the set may be empty, the vector may be zero, or the dimension may be zero.	Explicitly ask what the statement says when every quantity takes its smallest admissible value, and handle that case first if it behaves differently.
Assuming a uniqueness claim is settled by one example	medium	Exhibiting an object with the desired property and concluding it is the only one.	Uniqueness requires assuming two such objects and deriving their equality. Existence and uniqueness are separate obligations and are often proved by quite different means.

FAQs

What is the practical difference between a definition and a theorem?

A definition names a condition and is automatically a two-way street, so the term and the condition may be substituted for one another freely. A theorem asserts that one condition implies another and, unless it is stated as an equivalence, licenses substitution in one direction only. Confusing the two produces the converse error, which is the most common logical mistake in the subject.

Why must both directions of an if-and-only-if be proved?

Because the statement asserts two independent implications, and one can hold while the other fails. Every square with equal sides is a rectangle with equal sides, but not conversely for a general quadrilateral, and analogous asymmetries occur constantly in linear algebra. The two halves are also often of very unequal difficulty, so proving the easy one gives no assurance about the other.

How do I decide between a direct proof and its contrapositive?

Compare the two hypotheses. A direct proof starts from $P$ ; a contrapositive proof starts from $\neg Q$ . Whichever gives more concrete material to work with is usually the easier route. Negative conclusions such as the set is not independent often become positive hypotheses under contraposition, which is exactly when the technique pays.

What does it mean when a theorem says the following are equivalent?

It means every pair of the listed conditions may be connected by an if-and-only-if, so any one may be verified and all the others concluded. The proof is normally organised as a cycle of implications through the list, which requires only as many proofs as there are conditions. In practice these theorems are used to substitute a cheap test for an expensive one.

Is a constructive proof always preferable?

Where available, yes, because it yields an algorithm as well as a fact. But non-constructive proofs are often shorter and sometimes are the only ones known, and a fact established non-constructively is no less true. The distinction matters when the object is needed in practice: knowing that a basis exists is not the same as being able to produce one.

I have verified a claim on twenty random matrices. Is that a proof?

No. Numerical agreement on finitely many cases establishes nothing general, and in floating point it does not even establish those cases exactly. Testing is valuable for refuting false conjectures quickly and for building confidence before investing in a proof, but the roles must be labelled clearly and never conflated in a written argument.

How do I get started when a proof will not begin?

Rewrite the statement in if-then form, then replace every defined term in both the hypothesis and the conclusion by its definition. Write the hypothesis at the top of a page and the conclusion at the bottom and work towards the middle from both ends. If the direct route stalls, form the contrapositive and try again from there.

References

Beezer, R. A. A First Course in Linear Algebra, Version 0.70. University of Puget Sound, 2006. Proof technique material distributed across Sections SSLE, RREF, TSS, NSM, VO, LC and MO. Licensed under the GNU Free Documentation License v1.2.
ISO 80000-2:2019, Quantities and units — Part 2: Mathematics. International Organization for Standardization.
Velleman, D. J. How to Prove It: A Structured Approach, 3rd edition. Cambridge University Press, 2019.
Polya, G. How to Solve It. Princeton University Press, 1945. The forward-and-backward search strategy in its original form.
ISO/IEC/IEEE 29148:2018, Systems and software engineering — Life cycle processes — Requirements engineering.
Halmos, P. R. How to Write Mathematics. L'Enseignement Mathematique, 1970. On directionality, naming and the rewrite that follows discovery.

AI Suggested Questions

Give me a linear algebra theorem whose converse is false, together with the smallest counterexample that shows it.
Rewrite a six-condition equivalence theorem as a cycle of implications and justify the ordering you chose.
Show a proof that appears to work but fails because one manipulation was irreversible, and identify the exact step.
How would a proof assistant formalise the double-inclusion argument for a null space equality, and what obligations does it generate?
Take a theorem with three hypotheses and construct three examples, each violating exactly one hypothesis, showing the conclusion fails.
What is the correct contrapositive of a statement whose conclusion has two clauses joined by and, and why is it easy to get wrong?

Related Calculators

Implication & Contrapositive Tool

Enter a compound statement and see its contrapositive, converse, inverse and correct negation side by side.

Equivalence Cycle Planner

Given a list of conditions, count the pairwise equivalences implied and lay out a minimal cycle of implications covering them.

Counterexample Search Tool

Test a proposed matrix identity or implication over small exact integer examples and report the first violation found.

Overview

Definition

Definition as a Two-Way Implication

Theorem, Hypothesis and Conclusion

Equivalence (Characterisation)

Contrapositive and Converse

Concepts

Set equality by double inclusion

Proving an identity as a justified chain

Uniqueness by assuming two

Cycles for lists of equivalent conditions

Constructive proofs carry algorithms

Decomposition as a proof strategy

Language discipline and object types

Selecting a technique from the shape of the conclusion

Equations

Variable Definitions

Worked Numerical Example

Problem statement

Identify the shape of the statement

Expand every definition

Forward half: assume independence

Forward half: do not skip the reverse inclusion

Reverse half: assume the null space is trivial

Reverse half: conclude independence

Record the contrapositive form for later use

Note what the result buys

Applications &amp; Industry Use

Proof obligations and specification contracts

Assurance cases and necessary versus sufficient conditions

Acceptance criteria as equivalences

Lists of equivalent characterisations

Constructive existence proofs as reference algorithms

Uniqueness arguments and counterexample search

Design Considerations

Let the conclusion choose the technique

Explore backwards, write forwards

Never assume the converse of a theorem

State and honour every hypothesis

Test a conjecture computationally before proving it

Write with named objects, not pronouns

Standards &amp; Codes

Material Selection

Manufacturing Notes

A practical order of operations for writing a proof

Cost of the cycle strategy for equivalences

Where computation belongs in an argument

Recognising a proof that will become an algorithm

Reviewing someone else's proof

Failure Modes &amp; Common Mistakes

FAQs

Related Engineering Topics

References

AI Suggested Questions

Related Calculators

Continue learning

Applications & Industry Use

Standards & Codes

Failure Modes & Common Mistakes