Thirty-three miniatures

Mathematical and algorithmic applications of linear algebra

by Jiri Matousek

Errata

For both the 1st and 2nd printing

• M9 page 29, "Lehmmens" should be "Lemmens". (Noted by Norihide Tokushige.)
• M22 page 88, concerning 2-connected graphs, for Lemma B we really need vertex 2-connected graphs, while the property of every edge lying in a cycle is equivalent to edge 2-connectedness. Thus, by 2-connected we mean a graph that remains connected after removing an arbitrary vertex. (Noted by Norihide Tokushige.)
• M29, the concluding remark: it refers to the lower bound of \sqrt{2m} from the lemma, but the lower bound that is really needed is 2\sqrt m. This stronger lower bound is proved in Alon's paper, and the lemma claims the weaker result of \sqrt{2m} because the proof is slightly simpler. (Noted by Boris Bukh.)
• M33 page 172, proof of the claim, the linear independence of the vectors v_1,...,v_d is written erroneously. Really we need that the d x d matrix V whose i-th row is v_i is nonsingular. One way seeing it is via the Vandermonde determinant. The trick with roots of a polynomial in the text can also be applied to the linear system Va=0, to show that the only solution is a=0 (but the linear system expressing the linear independence of the v_i directly is V^T a=0). (Noted by Norihide Tokushige.)

The following ones have been corrected in the 2nd printing (2012)

• M9 page 28 line 3: "more that" should be "more than" (Noted by Norihide Tokushige.)
• M9 page 28 line -7: all i,j. should be all j. (Noted by Norihide Tokushige.)
• M9 page 29 line -4: "The best upper bound" should be "The best lower bound" (Noted by Norihide Tokushige.)
• M14 page 49: bottom, the definitions of rho_1 and rho_2 should be swapped. (Noted by Norihide Tokushige.)
• M17 page 58: proof of the corollary: the denominator in the first identity is n-k+1, not n-k (but this doesn't influence the subsetquent estimates). (Noted by Norihide Tokushige.)
• M17 page 59 in the middle: "(ii) fA ..." should be "(ii) f_A ..." (Noted by Norihide Tokushige.)
• M21 page 82, 4th line of the proof of the corollary, spanning tree of G (instead of D). (Noted by Norihide Tokushige.)
• M22 page 87, displayed formula, \pi_2 should be \pi(2). (Noted by Martin J. Erickson.)
• M22 page 88, concerning 2-connected graphs, for Lemma B we really need vertex 2-connected graphs, while the property of every edge lying in a cycle is equivalent to edge 2-connectedness. Thus, by 2-connected we mean a graph that remains connected after removing an arbitrary vertex. (Noted by Norihide Tokushige.)
• M24 page 110 line 2 page "a bipartite matching in a given graph" should be "a parfect matching in a given bipartite graph". (Noted by Norihide Tokushige.)
• M25 page 118, second line, the inequality dq^(n-1) \leq (q-1)q^n should be dq^(n-1) \leq (q-1)q^(n-1). (Noted by Nitesh Jha.)
• M28 page 136, line -5 in the proof: "v_1 in H_1, v_2 in H_2" should be "v_1 in V(H_1), v_2 in V(H_2)". (Noted by Norihide Tokushige.)
• M29 page 144, line 4, V(H) should be V(G). (Noted by Norihide Tokushige.)
• M30 page 149, 1st line in the 3rd pargraph: f_{d,1} should be f_{d,q}. (Noted by Norihide Tokushige.)
• M31, page 158, 3rd line: Fischer misspelled Fisher. (Noted by Norihide Tokushige.)
• M31, page 160: In the last line of the chain of inequalities, the final term should be (n/(2\sqrt 2))||w||.||u||, rather than (n/4)||u||^2. The latter is correct but it is not what one needs to derive inequality (30). (Noted by Torsten Sander.)
• M32, page 167: The final term in the inequality chain should have d/n under the root, not n/d. (Noted by Torsten Sander.) i
• M32, page 169 Yujobo misspelled (Yubojo). (Noted by Norihide Tokushige.)
• M33, page 174: The first line of the proof mentions the set {1,...,k}, but it should be {1,...,d}. (Noted by Torsten Sander.)
• M33, page 176: The summation at the top of the page should range to d, not n. (Noted by Torsten Sander.)
• M33, page 177, the second last line in the proof, the subscripts i should be j. (Noted by Norihide Tokushige.)

Comments are greatly appreciated (mistakes, missing references, passages that are confusing or difficult to understand...). Please mail your comments to "matousek" at the address "kam.mff.cuni.cz".