Unit 1.1 · about 6 h
51 / 324Proof habits and shape notation
A correct calculation can still answer the wrong quantified question. Proof habits make the assumptions behind every later decomposition and solver visible.
- explain
- derive
You can now
- Translate a linear-algebra claim between prose, quantifiers, indexed sums and explicit shapes.
- Prove an implication in both directions when needed, and identify where its assumptions enter.
- Use contradiction, induction or a small counterexample rather than treating numerical tests as proofs.
Covers
- Definitions, quantifiers, implications and counterexamples
- Scalars, vectors, matrices and tensor shape notation
Study, in this order
3 steps
- Mathematics for Computer Science: proof templates and notationMIT 6.042J - Proof strand
Lehman, Leighton and Meyer, Chapter 1, sections 1.1 to 1.9 (pp. 5 to 19); Chapter 3, sections 3.1 (pp. 42 to 45) and 3.6 (pp. 56 to 61); sections 4.1 to 4.4 (pp. 81 to 93)
Depth · In Chapter 4, read the definitions of sets, sequences, functions and relations. Leave cardinality and the remaining logical-circuit material.
- Induction and invariantsMIT 6.042J - Proof strand
Chapter 5, sections 5.1 to 5.3 (pp. 115 to 130), then 5.4.1 to 5.4.3 (pp. 130 to 136)
Depth · Read the ordinary and strong induction templates and the robot invariant. Stop before the later state-machine applications.
- Vectors, matrices and indexed productsMathematics for Machine Learning
Chapter 2, section 2.2 (pp. 22 to 27), especially the indexed matrix-product definition on p. 22
Depth · Use this as notation repair, not a second first pass. Treat a tensor here as an array with an ordered list of axis sizes; multilinear tensor theory is outside this unit.
Focus on
- Declare domains before quantifiers. Negating 'for every \(x\), \(P(x)\)' gives 'there exists \(x\) with not \(P(x)\)', not 'every \(x\) fails'.
- Separate an implication, its converse and its contrapositive. An iff requires both directions.
- For \(A\) of shape \((m,n)\), write \((Ax)_i=\sum_j A_{ij}x_j\) with \(x\) in \(\mathbb{R}^n\). Distinguish a scalar, a vector, a column matrix and an array with extra axes.
- An induction proof needs a starting case and a step for every permitted index. An invariant needs initialization and preservation.
Reproduce closed-book
A=np.array([[1,2],[2,4]],dtype=np.float64) and z=np.array([-2,1],dtype=np.float64), with no random draws. Compute np.linalg.norm(A@z,2): the reference run gives 0.0, below 1e-12. The nonzero witness \(z\) refutes independence for this \(A\); the numerical check does not prove the general iff.Traps
- Checking several vectors cannot establish a claim about all real vectors. One exact counterexample can refute it.
- Swapping 'for every \(b\) there exists \(x\)' with 'there exists \(x\) for every \(b\)' changes solvability into a much stronger claim.
- A vector of mathematical shape \(n\) is not automatically a NumPy
(n,1)column. Write the storage shape separately.
Practice
6.042J text: Problem 1.3(a), a bogus inequality proof
Chapter 1, Problem 1.3(a), printed p. 21
Identify the first invalid step and repair the direction of the inequality. Then annotate the two linear-algebra proofs in reproduce with the assumption used at each step.
Self-test
-
Where do the assumptions enter the independence iff proof?
\(A\) has \(n\) columns in \(\mathbb{R}^m\), so \(Ax\) is the same linear combination used in the definition. Independence forces all coefficients \(x_j\) to vanish in the forward direction. In the reverse direction, the assumed trivial kernel forces the coefficients of any zero combination to vanish. Neither direction requires \(A\) to be square. -
Negate: for every \(b\) in \(\mathbb{R}^m\) there exists \(x\) in \(\mathbb{R}^n\) with \(Ax=b\).
There exists \(b\) in \(\mathbb{R}^m\) such that for every \(x\) in \(\mathbb{R}^n\), \(Ax\) is not \(b\). This is one unattainable right-hand side, not a statement that every \(b\) is unattainable. -
Why does the transpose-power induction start at zero, and what does its step use?
For square \(A\), \(A^0=I\) and \(I^\top=I\) establish \(k=0\). If the claim holds at \(k\), then \((A^{k+1})^\top=(A^k A)^\top=A^\top(A^k)^\top=A^\top(A^\top)^k=(A^\top)^{k+1}\). Squareness makes the powers defined; the induction hypothesis is used at the third equality. -
Is \(T(x)=x+c\) linear for a fixed nonzero vector \(c\)?
No. Every linear map sends zero to zero, but \(T(0)=c\). Nonzero \(c\) is the assumption used to obtain the contradiction.
Completion criterion
Stop when
You can write the iff and transpose-power proofs without notes, negate the solvability claim with the domains intact, and explain why the NumPy witness is a refutation rather than a universal proof.
Mark passed, then open 1.2 Only mark this when you can do it without notes.Leads to
- 1.2 Linear maps, span, independence and change of basis Use definitions to prove linearity and independence.
- 1.1 Cost models, asymptotic notation and cases Apply quantifier discipline to asymptotic bounds.
Resources for this unit
- MIT 6.042J - Proof strand Study textbook Chapters 1 and 3, §§4.1-4.4 and §§5.1-5.4 with matching Unit 1 problems. Leave the rest of the course.
- Mathematics for Machine Learning Use Chapters 2-4 and §10.2 to check notation or re-derive a result. Do not treat it as a second course.
Also in this section
- MIT 18.06 - Linear Algebra Follow lectures 1-10, 14-17, 21-22, 25, 27, 29-31 and 33 with matching problems. This is the ordered first pass.
- MIT 18.065 - Applied matrix bridge Use lectures 3-10 after 18.06 for SVD, PCA, low-rank approximation, matrix norms and solver difficulty.
- Introduction to Applied Linear Algebra Sample Chapters 1-13 and the extra exercises for computational practice in fitting, least squares and pseudoinverses.
- Essence of Linear Algebra Open only when a geometric picture is missing; it does not replace derivation or problem solving.
- NumPy broadcasting and matmul shape rules Read General broadcasting rules and Broadcastable arrays, then
matmulNotes for stacked matrices and one-dimensional promotion. These close the pool's array-semantics gap. - Fundamentals of Numerical Computation: conditioning and operation counts Python edition, section 2.8 through Residual and backward error for the fixed-matrix perturbation bound; section 2.5.3 for triangular-solve and LU flop counts. Use Exercise 2.8.7 for a condition-number proof, not the unseeded Hilbert experiment.