Ch.8: Applications

Chapter 8 of the book "No Bullshit Guide to Linear Algebra" by Ivan Savov Balancing chemical equations Input–output models in economics Electric circuits Graphs Fibonacci sequence Linear programming Least squares approximate solutions Computer graphics Cryptography Error correcting codes Fourier analysis

194 flashcards · Mathematics · by lakesare

Part of Textbooks › No Bullshit Guide to Linear Algebra (Ivan Savov) · 10 courses

  1. [Applications] Before starting a project that applies linear algebra, what check does Savov ask you to make?

    An ethics check: could the work be used to harm people? Some uses are clearly harmful (weapons, financial scams); others are dual-use, e.g. a satellite localization service for finding missing people can also be used by governments to spy on citizens.

  2. [Balancing chemical equations] When is a chemical equation balanced?

    Each type of atom appears the same number of times on both sides. Coefficients in front of the reactants and products are chosen to achieve this.Example: 2H2+O2→2H2O2\mathrm{H_2} + \mathrm{O_2} \to 2\mathrm{H_2O}2H2​+O2​→2H2​O has 4 H atoms and 2 O atoms on each side; H2+O2→H2O\mathrm{H_2} + \mathrm{O_2} \to \mathrm{H_2O}H2​+O2​→H2​O is not balanced.

  3. [Balancing chemical equations] How many molecules of each type a reaction consumes and produces, relative to each other, are its stoichiometric ratios.

    Example: in 2H2+O2→2H2O2\mathrm{H_2} + \mathrm{O_2} \to 2\mathrm{H_2O}2H2​+O2​→2H2​O , two hydrogen molecules are needed per oxygen molecule.

  4. [Balancing chemical equations] How do you find the coefficients a,b,c,da, b, c, da,b,c,d that balance a CH4+b O2→c CO2+d H2Oa\,\mathrm{CH_4} + b\,\mathrm{O_2} \to c\,\mathrm{CO_2} + d\,\mathrm{H_2O}aCH4​+bO2​→cCO2​+dH2​O with linear algebra?

    Write one linear equation per type of atom, then solve the null space problem Ax⃗=0⃗A\vec{x} = \vec{0}Ax=0 for x⃗=(a,b,c,d)\vec{x} = (a, b, c, d)x=(a,b,c,d) . C: a=ca = ca=c ; H: 4a=2d4a = 2d4a=2d ; O: 2b=2c+d2b = 2c + d2b=2c+d . Moving everything to the left side: A=[10−10400−202−2−1]A = \begin{bmatrix} 1 & 0 & -1 & 0 \\ 4 & 0 & 0 & -2 \\ 0 & 2 & -2 & -1 \end{bmatrix}A=⎣⎡​140​002​−10−2​0−2−1​⎦⎤​

  5. [Balancing chemical equations] In the matrix AAA of a balancing problem Ax⃗=0⃗A\vec{x} = \vec{0}Ax=0 ( x⃗\vec{x}x = the coefficients), what are the rows, the columns, and the entries?

    Row = one type of atom, column = one molecule; entry = the number of those atoms in that molecule, negated for products. Example: in a CH4+b O2→c CO2+d H2Oa\,\mathrm{CH_4} + b\,\mathrm{O_2} \to c\,\mathrm{CO_2} + d\,\mathrm{H_2O}aCH4​+bO2​→cCO2​+dH2​O , the H row is (4,0,0,−2)(4, 0, 0, -2)(4,0,0,−2) .

  6. [Balancing chemical equations] Balance CH4+O2→CO2+H2O\mathrm{CH_4} + \mathrm{O_2} \to \mathrm{CO_2} + \mathrm{H_2O}CH4​+O2​→CO2​+H2​O (combustion of methane).

    CH4+2 O2→CO2+2 H2O\boldsymbol{\mathrm{CH_4} + 2\,\mathrm{O_2} \to \mathrm{CO_2} + 2\,\mathrm{H_2O}}CH4​+2O2​→CO2​+2H2​O The RREF of the coefficient matrix has 3 pivots and 1 free variable, and the null space is span⁡{(12,1,12,1)}\operatorname{span}\{(\frac{1}{2}, 1, \frac{1}{2}, 1)\}span{(21​,1,21​,1)} . Chemists use integer coefficients, so multiply by 2.

  7. [Balancing chemical equations] Why does a balancing problem Ax⃗=0⃗A\vec{x} = \vec{0}Ax=0 have infinitely many solutions x⃗\vec{x}x (the coefficients)?

    Multiplying all coefficients by the same number keeps a balanced equation balanced, so every multiple of a solution is a solution. For methane combustion the solutions form a one-dimensional null space, span⁡{(12,1,12,1)}\operatorname{span}\{(\frac{1}{2}, 1, \frac{1}{2}, 1)\}span{(21​,1,21​,1)} .

  8. [Balancing chemical equations] CH4+2 O2→CO2+2 H2O\mathrm{CH_4} + 2\,\mathrm{O_2} \to \mathrm{CO_2} + 2\,\mathrm{H_2O}CH4​+2O2​→CO2​+2H2​O How many O2\mathrm{O_2}O2​ molecules are consumed and how many CO2\mathrm{CO_2}CO2​ molecules are produced when 1000 methane molecules burn?

    2000 O2\mathrm{O_2}O2​ consumed, 1000 CO2\mathrm{CO_2}CO2​ produced. The coefficients give the amounts per "unit of reaction"; here there are 1000 units.

  9. [Balancing chemical equations] Once a chemical equation is balanced, what other quantities can be expressed per "unit of reaction"?

    Physical quantities of the reaction, such as the energy it releases. Example: CH4+2 O2→CO2+2 H2O+890 [kJ/mol]\mathrm{CH_4} + 2\,\mathrm{O_2} \to \mathrm{CO_2} + 2\,\mathrm{H_2O} + 890\,[\mathrm{kJ/mol}]CH4​+2O2​→CO2​+2H2​O+890[kJ/mol] : burning 1 mol ( 6.022×10236.022 \times 10^{23}6.022×1023 molecules) of methane releases 890 kJ of heat.

  10. [Input–output models in economics] What equation does a Leontief input–output model state for the production rates x⃗\vec{x}x of an economy's commodities?

    x⃗=d⃗+Ax⃗\boldsymbol{\vec{x} = \vec{d} + A\vec{x}}x=d+Ax : production = external demand d⃗\vec{d}d + internal demand Ax⃗A\vec{x}Ax . aija_{ij}aij​ = units of commodity iii used up per unit of commodity jjj produced.Example: producing each unit of aluminum uses 0.3 units of electric power, so aelec,alu=0.3a_{\text{elec},\text{alu}} = 0.3aelec,alu​=0.3 .

  11. [Input–output models in economics] How do you solve the input–output model x⃗=d⃗+Ax⃗\vec{x} = \vec{d} + A\vec{x}x=d+Ax for the production rates x⃗\vec{x}x ?

    x⃗=(1 ⁣ ⁣1−A)−1d⃗\boldsymbol{\vec{x} = (\mathrm{1\!\!1} - A)^{-1}\vec{d}}x=(11−A)−1d 1 ⁣ ⁣1x⃗=d⃗+Ax⃗ ⇒ (1 ⁣ ⁣1−A)x⃗=d⃗\mathrm{1\!\!1}\vec{x} = \vec{d} + A\vec{x} \;\Rightarrow\; (\mathrm{1\!\!1} - A)\vec{x} = \vec{d}11x=d+Ax⇒(11−A)x=d , where 1 ⁣ ⁣1\mathrm{1\!\!1}11 is the identity matrix.

  12. [Input–output models in economics] A country produces electric power xex_exe​ , wood xwx_wxw​ and aluminum xax_axa​ . External demands: 25, 10, 14 units. Each unit of wood uses 0.05 units of power and each unit of aluminum 0.3; each unit of power uses 0.01 units of wood and 0.1 of aluminum; each unit of aluminum uses 0.01 units of wood. Write this as x⃗=d⃗+Ax⃗\vec{x} = \vec{d} + A\vec{x}x=d+Ax .

    [xexwxa]=[251014]+[00.050.30.0100.010.100][xexwxa]\begin{bmatrix} x_e \\ x_w \\ x_a \end{bmatrix} = \begin{bmatrix} 25 \\ 10 \\ 14 \end{bmatrix} + \boldsymbol{\begin{bmatrix} 0 & 0.05 & 0.3 \\ 0.01 & 0 & 0.01 \\ 0.1 & 0 & 0 \end{bmatrix}} \begin{bmatrix} x_e \\ x_w \\ x_a \end{bmatrix}⎣⎡​xe​xw​xa​​⎦⎤​=⎣⎡​251014​⎦⎤​+⎣⎡​00.010.1​0.0500​0.30.010​⎦⎤​⎣⎡​xe​xw​xa​​⎦⎤​ Row iii lists what the production of each commodity uses of commodity iii .

  13. [Input–output models in economics] [xexwxa]=[251014]+[00.050.30.0100.010.100][xexwxa]\begin{bmatrix} x_e \\ x_w \\ x_a \end{bmatrix} = \begin{bmatrix} 25 \\ 10 \\ 14 \end{bmatrix} + \begin{bmatrix} 0 & 0.05 & 0.3 \\ 0.01 & 0 & 0.01 \\ 0.1 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_e \\ x_w \\ x_a \end{bmatrix}⎣⎡​xe​xw​xa​​⎦⎤​=⎣⎡​251014​⎦⎤​+⎣⎡​00.010.1​0.0500​0.30.010​⎦⎤​⎣⎡​xe​xw​xa​​⎦⎤​ (power, wood, aluminum)The solution is (xe,xw,xa)=(30.64,10.48,17.06)(x_e, x_w, x_a) = (30.64, 10.48, 17.06)(xe​…

    Producing aluminum (and wood) uses power. 25+0.05⋅10.48+0.3⋅17.06=25+0.52+5.12=30.6425 + 0.05 \cdot 10.48 + 0.3 \cdot 17.06 = 25 + 0.52 + 5.12 = 30.6425+0.05⋅10.48+0.3⋅17.06=25+0.52+5.12=30.64

  14. [Input–output models in economics] Who first applied linear algebra to model how the industries of an economy depend on each other?

    Wassily Leontief, who received the Nobel prize for it. Hence the name Leontief input–output model.

  15. [Electric circuits] What does Ohm's law say about a resistor?

    V=RI\boldsymbol{V = RI}V=RI : the voltage VVV across it equals its resistance RRR times the current III through it. Units: volts [V], amperes [A], ohms [Ω], with [Ω]=[V/A][\Omega] = [\mathrm{V/A}][Ω]=[V/A] .Example: R=2 [Ω]R = 2\,[\Omega]R=2[Ω] , I=3 [A]I = 3\,[\mathrm{A}]I=3[A] gives V=6 [V]V = 6\,[\mathrm{V}]V=6[V] .

  16. [Electric circuits] A 121 [Ω]121\,[\Omega]121[Ω] light bulb is connected to a 110 [V]110\,[\mathrm{V}]110[V] socket. Cables are rated for at most 0.5 A, 1 A and 2 A. Which is the lowest-rated cable you can use?

    The 1 A cable. I=VR=110121=0.909 [A]I = \frac{V}{R} = \frac{110}{121} = 0.909\,[\mathrm{A}]I=RV​=121110​=0.909[A] , which exceeds 0.5 A.

  17. [Electric circuits] What are Kirchhoff's two circuit laws?

    Kirchhoff's voltage law (KVL) The voltage gains and losses along any loop of the circuit sum to zero. Example: a loop with a 10 V battery and two resistors: 10−4−6=010 - 4 - 6 = 010−4−6=0 if the voltage drops across the resistors are 4 V and 6 V. Kirchhoff's current law (KCL) The total current flowing into a junction equals the total current flowing out of it. Example: 3 A flows into a junction and splits into two wires; if one carries 1 A, the other carries 2 A.

  18. [Electric circuits] Which conservation principles do Kirchhoff's voltage law (gains and losses around a loop sum to zero) and current law (current in = current out at a junction) express?

    Voltage law: conservation of energy. Current law: conservation of charge. Electrons gain potential in batteries and lose it in resistors (as heat), and return to their starting potential after a full loop. Charge is neither created nor destroyed at a junction.

  19. [Electric circuits] What does it mean to solve an electric circuit?

    Find the current in each wire and the voltage across each resistor.

  20. [Electric circuits] When labelling a resistor's sides "+" and "−" for a chosen current direction, which side gets "+", and why?

    The side where the current enters. The electric potential always drops across a resistor in the direction of the current.

  21. [Electric circuits] What are the steps of the branch current method for solving a circuit?

    Label currents Give each branch (wire between junctions) a current variable with a chosen direction. Mark polarities Put "+" on the side of each resistor where its current enters, "−" where it leaves. Write KVL and KCL equations One voltage-law equation per independent loop, current-law equations at junctions, until there are as many equations as unknowns. Solve Write the linear system as an augmented matrix and find its RREF (Gauss–Jordan elimination).

  22. [Electric circuits] Write the two KVL equations (loops A-B-C-D-A and A-F-E-D-A) and the KCL equation at junction A for the branch currents I1,I2,I3I_1, I_2, I_3I1​,I2​,I3​ .

    10−R1I2+5−R2I1=0\boldsymbol{10 - R_1 I_2 + 5 - R_2 I_1 = 0}10−R1​I2​+5−R2​I1​=0 , −20−R3I3−R2I1=0\ \boldsymbol{-20 - R_3 I_3 - R_2 I_1 = 0} −20−R3​I3​−R2​I1​=0 , I1=I2+I3\ \boldsymbol{I_1 = I_2 + I_3} I1​=I2​+I3​ Batteries give gains, resistors give drops RIR IRI . The 20 V battery counts as −20-20−20 : along A-F-E-D-A it is passed from its + side to its − side.

  23. [Electric circuits] A circuit's branch currents satisfy 10−R1I2+5−R2I1=010 - R_1 I_2 + 5 - R_2 I_1 = 010−R1​I2​+5−R2​I1​=0 , −20−R3I3−R2I1=0\ -20 - R_3 I_3 - R_2 I_1 = 0 −20−R3​I3​−R2​I1​=0 , I1=I2+I3\ I_1 = I_2 + I_3 I1​=I2​+I3​ .Solve for I1,I2,I3I_1, I_2, I_3I1​,I2​,I3​ with R1=1R_1 = 1R1​=1 , R2=2R_2 = 2R2​=2 , R3=1R_3 = 1R3​=1 [Ω].

    I1=−1, I2=17, I3=−18\boldsymbol{I_1 = -1, \; I_2 = 17, \; I_3 = -18}I1​=−1,I2​=17,I3​=−18 [A] [−2−10−15−20−1201−1−10]undefinedRREF[100−101017001−18]\left[\begin{array}{ccc|c} -2 & -1 & 0 & -15 \\ -2 & 0 & -1 & 20 \\ 1 & -1 & -1 & 0 \end{array}\right] \xrightarrow{\text{RREF}} \left[\begin{array}{ccc|c} 1 & 0 & 0 & -1 \\ 0 & 1 & 0 & 17 \\ 0 & 0 & 1 & -18 \end{array}\right]⎣⎡​−2−21​−10−1​0−1−1​−15200​⎦⎤​RREF​⎣⎡​100​010​001​−117−18​⎦⎤​

  24. [Electric circuits] Solving a circuit gives a branch current I3=−18 [A]I_3 = -18\,[\mathrm{A}]I3​=−18[A] . What does the minus sign mean?

    18 A flows opposite to the direction chosen for I3I_3I3​ . So the voltage across that resistor also has the reverse of the polarity marked.

  25. [Electric circuits] In the loop current method, what are the unknowns?

    One current per small loop of the circuit, circulating around that loop (e.g. all clockwise). A resistor on the boundary of two loops carries both loop currents. R2R_2R2​ carries I1I_1I1​ downward and I2I_2I2​ upward.

  26. [Electric circuits] Loop currents I1I_1I1​ (left loop) and I2I_2I2​ (right loop) both circulate clockwise, so the shared resistor R2R_2R2​ carries I1I_1I1​ in one direction and I2I_2I2​ in the other.What voltage term does R2R_2R2​ contribute to the KVL equation of the left loop, and why?

    −R2(I1−I2)\boldsymbol{-R_2(I_1 - I_2)}−R2​(I1​−I2​) V=RIV = RIV=RI is linear in III , so the effects of the two currents add (the superposition principle): a drop −R2I1-R_2 I_1−R2​I1​ and a gain +R2I2+R_2 I_2+R2​I2​ .

  27. [Electric circuits] Write the KVL equations for the loop currents I1,I2I_1, I_2I1​,I2​ and solve them for R1=1R_1 = 1R1​=1 , R2=2R_2 = 2R2​=2 , R3=1R_3 = 1R3​=1 [Ω].

    10−R1I1+5−R2(I1−I2)=010 - R_1 I_1 + 5 - R_2(I_1 - I_2) = 010−R1​I1​+5−R2​(I1​−I2​)=0 , R2(I1−I2)−R3I2+20=0\ R_2(I_1 - I_2) - R_3 I_2 + 20 = 0 R2​(I1​−I2​)−R3​I2​+20=0 ; I1=17I_1 = 17I1​=17 , I2=18I_2 = 18I2​=18 [A] Rearranged: 3I1−2I2=153 I_1 - 2 I_2 = 153I1​−2I2​=15 , 2I1−3I2=−20\ 2 I_1 - 3 I_2 = -20 2I1​−3I2​=−20 . R2R_2R2​ carries I1−I2=−1I_1 - I_2 = -1I1​−I2​=−1 A downward, as found with branch currents.

  28. [Electric circuits] This circuit has three loops: two small ones and the outer one. Why do the three KVL equations not determine more than two loop currents?

    The outer loop's equation is the sum of the two small loops' equations, so the three equations are linearly dependent. (10−R1I1+5−R2(I1−I2))+(R2(I1−I2)−R3I2+20)=10−R1I1+5−R3I2+20(10 - R_1 I_1 + 5 - R_2(I_1 - I_2)) + (R_2(I_1 - I_2) - R_3 I_2 + 20) = 10 - R_1 I_1 + 5 - R_3 I_2 + 20(10−R1​I1​+5−R2​(I1​−I2​))+(R2​(I1​−I2​)−R3​I2​+20)=10−R1​I1​+5−R3​I2​+20 . KVL equations must come from linearly independent loops.

  29. [Electric circuits] Besides electric currents, which flows in networks can be computed with the same matrix technique?

    Any flow with a conservation law at the nodes, e.g. cars on city streets, goods between economies, data packets through the Internet. Each network has its own law for the flow, but the result is again a system of linear equations.

  30. [Graphs] What is a graph G=(V,E)G = (V, E)G=(V,E) ?

    A set VVV of vertices and a set EEE of edges, where an edge from vertex iii to vertex jjj is the pair (i,j)(i, j)(i,j) . Example: websites (vertices) and the hyperlinks between them (edges).

  31. [Graphs] What is the adjacency matrix AAA of a graph with vertices 1,…,n1, \dots, n1,…,n ?

    The n×nn \times nn×n matrix with Aij=1A_{ij} = 1Aij​=1 if the edge (i,j)(i, j)(i,j) exists and Aij=0A_{ij} = 0Aij​=0 otherwise. Vertex iii corresponds to row iii (and column iii ), so no separate labels are needed.

  32. [Graphs] Write the adjacency matrix of this graph.

    A=[0110000100000011000110000]A = \boldsymbol{\begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \end{bmatrix}}A=⎣⎡​00011​10000​11000​00000​00110​⎦⎤​ E={(1,2),(1,3),(2,3),(3,5),(4,1),(4,5),(5,1)}E = \{(1,2), (1,3), (2,3), (3,5), (4,1), (4,5), (5,1)\}E={(1,2),(1,3),(2,3),(3,5),(4,1),(4,5),(5,1)}

  33. [Graphs] AAA is the adjacency matrix of a graph. What does the entry (A2)ij(A^2)_{ij}(A2)ij​ count, and why?

    The number of ways to go from vertex iii to vertex jjj in exactly two steps. (A2)ij=∑kAikAkj(A^2)_{ij} = \sum_k A_{ik} A_{kj}(A2)ij​=∑k​Aik​Akj​ , and AikAkj=1A_{ik} A_{kj} = 1Aik​Akj​=1 exactly when both edges (i,k)(i, k)(i,k) and (k,j)(k, j)(k,j) exist.

  34. [Graphs] AAA is the adjacency matrix of a graph. What does the entry (1 ⁣ ⁣1+A+A2)ij(\mathrm{1\!\!1} + A + A^2)_{ij}(11+A+A2)ij​ count?

    The number of ways to go from vertex iii to vertex jjj in zero, one or two steps. 1 ⁣ ⁣1\mathrm{1\!\!1}11 (identity) counts the zero-step way of staying at iii .

  35. [Graphs] For this graph, (1 ⁣ ⁣1+A+A2)41=2(\mathrm{1\!\!1} + A + A^2)_{41} = 2(11+A+A2)41​=2 ( AAA = adjacency matrix). Which are the two ways?

    The edge (4,1)(4, 1)(4,1) , and the edges (4,5),(5,1)(4, 5), (5, 1)(4,5),(5,1) .

  36. [Graphs] For this graph, column 4 of 1 ⁣ ⁣1+A+A2\mathrm{1\!\!1} + A + A^211+A+A2 ( AAA = adjacency matrix) is (0,0,0,1,0)T(0, 0, 0, 1, 0)^{\mathsf{T}}(0,0,0,1,0)T . What does that say about vertex 4?

    Vertex 4 has no inbound edges: it can be reached only by starting there. The single 1 is the zero-step way of starting at vertex 4.

  37. [Graphs] Which algorithm uses the adjacency matrix of the Web to compute an importance rank for each webpage?

    Google's PageRank.

  38. [Fibonacci sequence] How is the Fibonacci sequence a0,a1,a2,…a_0, a_1, a_2, \dotsa0​,a1​,a2​,… defined?

    a0=0, a1=1, an=an−1+an−2\boldsymbol{a_0 = 0, \; a_1 = 1, \; a_n = a_{n-1} + a_{n-2}}a0​=0,a1​=1,an​=an−1​+an−2​ for n≥2n \ge 2n≥2 . 0,1,1,2,3,5,8,13,21,34,55,…0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots0,1,1,2,3,5,8,13,21,34,55,…

  39. [Fibonacci sequence] A formula that gives each term of a sequence in terms of the terms before it is a recurrence relation.

    Example: an=an−1+an−2a_n = a_{n-1} + a_{n-2}an​=an−1​+an−2​ for the Fibonacci numbers.

  40. [Fibonacci sequence] Write the Fibonacci recurrence an+1=an+an−1a_{n+1} = a_n + a_{n-1}an+1​=an​+an−1​ as a matrix product.

    [an+1an]=[1110][anan−1]\begin{bmatrix} a_{n+1} \\ a_n \end{bmatrix} = \boldsymbol{\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}} \begin{bmatrix} a_n \\ a_{n-1} \end{bmatrix}[an+1​an​​]=[11​10​][an​an−1​​] The second row just copies ana_nan​ .

  41. [Fibonacci sequence] [an+1an]=A[anan−1]\begin{bmatrix} a_{n+1} \\ a_n \end{bmatrix} = A \begin{bmatrix} a_n \\ a_{n-1} \end{bmatrix}[an+1​an​​]=A[an​an−1​​] with A=[1110]A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}A=[11​10​] , a0=0a_0 = 0a0​=0 , a1=1a_1 = 1a1​=1 (Fibonacci numbers).Express aNa_NaN​ using ANA^NAN .

    aN=(0,1) AN(1,0)T\boldsymbol{a_N = (0, 1)\, A^N (1, 0)^{\mathsf{T}}}aN​=(0,1)AN(1,0)T AN(a1,a0)T=(aN+1,aN)TA^N (a_1, a_0)^{\mathsf{T}} = (a_{N+1}, a_N)^{\mathsf{T}}AN(a1​,a0​)T=(aN+1​,aN​)T with (a1,a0)=(1,0)(a_1, a_0) = (1, 0)(a1​,a0​)=(1,0) , and the dot product with (0,1)(0, 1)(0,1) selects the second entry.Example: A5=[8553]A^5 = \begin{bmatrix} 8 & 5 \\ 5 & 3 \end{bmatrix}A5=[85​53​] , so a5=(0,1)(8,5)T=5a_5 = (0, 1)(8, 5)^{\mathsf{T}} = 5a5​=(0,1)(8,5)T=5 .

  42. [Fibonacci sequence] What are the eigenvalues of the Fibonacci matrix A=[1110]A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}A=[11​10​] ?

    φ=1+52≈1.618\boldsymbol{\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618}φ=21+5​​≈1.618 (the golden ratio) and −1φ=1−52≈−0.618\boldsymbol{-\frac{1}{\varphi} = \frac{1 - \sqrt{5}}{2} \approx -0.618}−φ1​=21−5​​≈−0.618 They are the roots of the characteristic polynomial λ2−λ−1\lambda^2 - \lambda - 1λ2−λ−1 .Eigenvectors: (1,1φ)(1, \frac{1}{\varphi})(1,φ1​) and (1,−φ)(1, -\varphi)(1,−φ) , the columns of QQQ in A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 .

  43. [Fibonacci sequence] A=QΛQ−1A = Q \Lambda Q^{-1}A=QΛQ−1 is an eigendecomposition ( Λ\LambdaΛ diagonal). Why is AN=QΛNQ−1A^N = Q \Lambda^N Q^{-1}AN=QΛNQ−1 ?

    In QΛQ−1 QΛQ−1⋯QΛQ−1Q\Lambda Q^{-1} \, Q\Lambda Q^{-1} \cdots Q\Lambda Q^{-1}QΛQ−1QΛQ−1⋯QΛQ−1 every inner Q−1QQ^{-1}QQ−1Q equals 1 ⁣ ⁣1\mathrm{1\!\!1}11 . ΛN\Lambda^NΛN only needs the NNN -th powers of the eigenvalues on the diagonal.

  44. [Fibonacci sequence] Fibonacci numbers: aN=(0,1) AN(1,0)Ta_N = (0, 1)\, A^N (1, 0)^{\mathsf{T}}aN​=(0,1)AN(1,0)T with A=[1110]=QΛQ−1A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = Q \Lambda Q^{-1}A=[11​10​]=QΛQ−1 , Λ=diag⁡(φ,−1φ)\Lambda = \operatorname{diag}(\varphi, -\frac{1}{\varphi})Λ=diag(φ,−φ1​) .What is the advantage of computing aNa_NaN​ as (0,1) QΛNQ−1(1,0)T(0, 1)\, Q \Lambda^N Q^{-1} (1, 0)^{\mathsf{T}}(0,1)QΛNQ−1(1,0)T ?

    The number of operations does not depend on NNN , while the recurrence an=an−1+an−2a_n = a_{n-1} + a_{n-2}an​=an−1​+an−2​ takes about NNN steps. Steps: compute ΛN\Lambda^NΛN , multiply by Q−1Q^{-1}Q−1 and (1,0)T(1, 0)^{\mathsf{T}}(1,0)T on the right, by QQQ and (0,1)(0, 1)(0,1) on the left.Example: a55=139583862445a_{55} = 139583862445a55​=139583862445 .

  45. [Fibonacci sequence] Why can't the eigenvalue formula aN=(0,1) QΛNQ−1(1,0)Ta_N = (0, 1)\, Q \Lambda^N Q^{-1} (1, 0)^{\mathsf{T}}aN​=(0,1)QΛNQ−1(1,0)T (with φ=1+52\varphi = \frac{1+\sqrt{5}}{2}φ=21+5​​ in Λ\LambdaΛ ) compute large Fibonacci numbers in constant time on a real computer?

    Computing φN\varphi^NφN is not a constant-time operation, and floating-point approximations of φ\varphiφ give wrong results for large NNN . Exact symbolic computation is not practical either, so the constant-time claim is only a theoretical result.

  46. [Linear programming] Why are optimization problems called "programming" problems (as in linear programming)?

    Early computers were used mainly to solve optimization problems.

  47. [Linear programming] What is linear programming?

    The study of optimization problems with a linear objective function and linear constraints.

  48. [Linear programming] What is the general form of a linear program in the variables x1,…,xnx_1, \dots, x_nx1​,…,xn​ ?

    Maximize c1x1+⋯+cnxnc_1 x_1 + \dots + c_n x_nc1​x1​+⋯+cn​xn​ subject to mmm constraints ai1x1+⋯+ainxn≤bia_{i1} x_1 + \dots + a_{in} x_n \le b_iai1​x1​+⋯+ain​xn​≤bi​ and x1,…,xn≥0x_1, \dots, x_n \ge 0x1​,…,xn​≥0 . Example: xjx_jxj​ = production rate of product jjj , cjc_jcj​ = its price, the objective = total revenue, the bib_ibi​ = limits on staff, production capacity, logistics.

  49. [Linear programming] What is the simplex algorithm?

    A systematic procedure for solving linear programs. Like Gauss–Jordan elimination, it uses row operations, here on a matrix-like structure called a tableau.

  50. [Linear programming] The simplex algorithm performs row operations on a matrix-like structure called a tableau.

  51. [Least squares approximate solutions] How many solutions can an equation Ax⃗=b⃗A\vec{x} = \vec{b}Ax=b have, and when?

    Exactly one When AAA is invertible. Example: [1002]x⃗=(1,4)\begin{bmatrix} 1 & 0 \\ 0 & 2 \end{bmatrix}\vec{x} = (1, 4)[10​02​]x=(1,4) only for x⃗=(1,2)\vec{x} = (1, 2)x=(1,2) . Infinitely many When AAA has a nonzero null space and some solution exists. Example: [11]x⃗=2\begin{bmatrix} 1 & 1 \end{bmatrix}\vec{x} = 2[1​1​]x=2 for all x⃗=(t,2−t)\vec{x} = (t, 2 - t)x=(t,2−t) . None When b⃗\vec{b}b is not in the column space C(A)\mathcal{C}(A)C(A) . Example: [11]x=(1,2)\begin{bmatrix} 1 \\ 1 \end{b…

  52. [Least squares approximate solutions] Ax⃗=b⃗A\vec{x} = \vec{b}Ax=b has no solution. What is its least squares approximate solution x⃗∗\vec{x}^*x∗ ?

    The x⃗\vec{x}x that makes ∥Ax⃗−b⃗∥\|A\vec{x} - \vec{b}\|∥Ax−b∥ as small as possible. So Ax⃗∗A\vec{x}^*Ax∗ is as close as possible to b⃗\vec{b}b .

  53. [Least squares approximate solutions] In linear regression on a dataset D={A,b⃗}D = \{A, \vec{b}\}D={A,b} of NNN observations, what are the rows of AAA and the entries of b⃗\vec{b}b ?

    Row iii of AAA = the observed features a⃗i\vec{a}_iai​ of item iii ; bib_ibi​ = its observed outcome. AAA is N×nN \times nN×n for nnn features, b⃗\vec{b}b is N×1N \times 1N×1 . The goal is to predict bbb for a new a⃗\vec{a}a .Example: a⃗i\vec{a}_iai​ = (purchase frequency, purchase value, payment promptness) of customer iii , bib_ibi​ = the customer's lifetime value.

  54. [Least squares approximate solutions] What is a linear model ym⃗y_{\vec{m}}ym​ for data with nnn features?

    ym⃗(x⃗)=m1x1+⋯+mnxn=m⃗⋅x⃗\boldsymbol{y_{\vec{m}}(\vec{x}) = m_1 x_1 + \dots + m_n x_n = \vec{m} \cdot \vec{x}}ym​(x)=m1​x1​+⋯+mn​xn​=m⋅x with nnn parameters m1,…,mnm_1, \dots, m_nm1​,…,mn​ .

  55. [Least squares approximate solutions] For a model ym⃗y_{\vec{m}}ym​ and a dataset of observations a⃗i\vec{a}_iai​ with outcomes bib_ibi​ ( i=1,…,Ni = 1, \dots, Ni=1,…,N ), what is the total squared error S(m⃗)S(\vec{m})S(m) ?

    S(m⃗)=∑i=1N∣ym⃗(a⃗i)−bi∣2\boldsymbol{S(\vec{m}) = \sum_{i=1}^{N} |y_{\vec{m}}(\vec{a}_i) - b_i|^2}S(m)=∑i=1N​∣ym​(ai​)−bi​∣2 Each term ei(m⃗)=∣ym⃗(a⃗i)−bi∣2e_i(\vec{m}) = |y_{\vec{m}}(\vec{a}_i) - b_i|^2ei​(m)=∣ym​(ai​)−bi​∣2 is the squared distance between prediction and observation.

  56. [Least squares approximate solutions] Why is the total squared error S(m⃗)=∑i∣ym⃗(a⃗i)−bi∣2S(\vec{m}) = \sum_i |y_{\vec{m}}(\vec{a}_i) - b_i|^2S(m)=∑i​∣ym​(ai​)−bi​∣2 a good quantity to minimize when fitting a model?

    S(m⃗)=0S(\vec{m}) = 0S(m)=0 exactly when the model predicts every bib_ibi​ correctly, and every over- or undershoot adds a penalty. The penalty grows quadratically with the size of the discrepancy.

  57. [Least squares approximate solutions] For a linear model ym⃗(x⃗)=m⃗⋅x⃗y_{\vec{m}}(\vec{x}) = \vec{m} \cdot \vec{x}ym​(x)=m⋅x and data {A,b⃗}\{A, \vec{b}\}{A,b} (rows of AAA = observations), write the total squared error S(m⃗)=∑i∣ym⃗(a⃗i)−bi∣2S(\vec{m}) = \sum_i |y_{\vec{m}}(\vec{a}_i) - b_i|^2S(m)=∑i​∣ym​(ai​)−bi​∣2 with matrices.

    S(m⃗)=∥Am⃗−b⃗∥2\boldsymbol{S(\vec{m}) = \|A\vec{m} - \vec{b}\|^2}S(m)=∥Am−b∥2 Am⃗A\vec{m}Am is the vector of all NNN predictions a⃗i⋅m⃗\vec{a}_i \cdot \vec{m}ai​⋅m .

  58. [Least squares approximate solutions] What equation does the least squares approximate solution m⃗∗\vec{m}^*m∗ of Am⃗≈b⃗A\vec{m} \approx \vec{b}Am≈b satisfy, and what is m⃗∗\vec{m}^*m∗ ?

    ATA m⃗∗=ATb⃗\boldsymbol{A^{\mathsf{T}}A\,\vec{m}^* = A^{\mathsf{T}}\vec{b}}ATAm∗=ATb , so m⃗∗=(ATA)−1ATb⃗\boldsymbol{\vec{m}^* = (A^{\mathsf{T}}A)^{-1}A^{\mathsf{T}}\vec{b}}m∗=(ATA)−1ATb . Obtained by multiplying Am⃗≈b⃗A\vec{m} \approx \vec{b}Am≈b by ATA^{\mathsf{T}}AT on the left.

  59. [Least squares approximate solutions] When is ATAA^{\mathsf{T}}AATA invertible (needed for m⃗∗=(ATA)−1ATb⃗\vec{m}^* = (A^{\mathsf{T}}A)^{-1}A^{\mathsf{T}}\vec{b}m∗=(ATA)−1ATb )?

    When the columns of AAA are linearly independent. This is usually the case for a tall and skinny data matrix (many more observations than features).

  60. [Least squares approximate solutions] What is the Moore–Penrose pseudoinverse A+A^+A+ of a matrix AAA with linearly independent columns?

    A+=(ATA)−1AT\boldsymbol{A^+ = (A^{\mathsf{T}}A)^{-1}A^{\mathsf{T}}}A+=(ATA)−1AT m⃗∗=A+b⃗\vec{m}^* = A^+\vec{b}m∗=A+b is the least squares approximate solution of Am⃗≈b⃗A\vec{m} \approx \vec{b}Am≈b . Not to be confused with A†A^\daggerA† .

  61. [Least squares approximate solutions] A+=(ATA)−1ATA^+ = (A^{\mathsf{T}}A)^{-1}A^{\mathsf{T}}A+=(ATA)−1AT , and A+A=1 ⁣ ⁣1A^+A = \mathrm{1\!\!1}A+A=11 .Applying A+A^+A+ to both sides of Am⃗≈b⃗A\vec{m} \approx \vec{b}Am≈b gives m⃗∗=A+b⃗\vec{m}^* = A^+\vec{b}m∗=A+b . Is Am⃗∗=b⃗A\vec{m}^* = \vec{b}Am∗=b ?

    Only if b⃗\vec{b}b is in the column space of AAA . Otherwise Am⃗∗≠b⃗A\vec{m}^* \ne \vec{b}Am∗=b ; m⃗∗\vec{m}^*m∗ is only optimal in the sense that it minimizes ∥Am⃗−b⃗∥2\|A\vec{m} - \vec{b}\|^2∥Am−b∥2 .

  62. [Least squares approximate solutions] Find the best linear model y(x)=mxy(x) = mxy(x)=mx for the data points (xi,bi)(x_i, b_i)(xi​,bi​) : (105,45),(113,63),(125,86),(137,118),(141,112),(153,169)(105, 45), (113, 63), (125, 86), (137, 118), (141, 112), (153, 169)(105,45),(113,63),(125,86),(137,118),(141,112),(153,169) .

    m∗≈0.792\boldsymbol{m^* \approx 0.792}m∗≈0.792 AAA is the column (105,…,153)T(105, \dots, 153)^{\mathsf{T}}(105,…,153)T , so m∗=(ATA)−1ATb⃗=∑xibi∑xi2=80409101478≈0.792m^* = (A^{\mathsf{T}}A)^{-1}A^{\mathsf{T}}\vec{b} = \frac{\sum x_i b_i}{\sum x_i^2} = \frac{80409}{101478} \approx 0.792m∗=(ATA)−1ATb=∑xi2​∑xi​bi​​=10147880409​≈0.792 . The line y=0.792xy = 0.792xy=0.792x must pass through the origin.

  63. [Least squares approximate solutions] What is the geometric meaning of the least squares solution m⃗∗\vec{m}^*m∗ of Am⃗≈b⃗A\vec{m} \approx \vec{b}Am≈b ?

    Am⃗∗A\vec{m}^*Am∗ is the point of the column space C(A)\mathcal{C}(A)C(A) closest to b⃗\vec{b}b ; the error vector e⃗∗=Am⃗∗−b⃗\vec{e}^* = A\vec{m}^* - \vec{b}e∗=Am∗−b is perpendicular to C(A)\mathcal{C}(A)C(A) .

  64. [Least squares approximate solutions] The least squares error vector e⃗∗=Am⃗∗−b⃗\vec{e}^* = A\vec{m}^* - \vec{b}e∗=Am∗−b is perpendicular to the column space C(A)\mathcal{C}(A)C(A) .How does this give the equation ATAm⃗∗=ATb⃗A^{\mathsf{T}}A\vec{m}^* = A^{\mathsf{T}}\vec{b}ATAm∗=ATb ?

    Perpendicular to C(A)\mathcal{C}(A)C(A) means in the left null space N(AT)\mathcal{N}(A^{\mathsf{T}})N(AT) : AT(Am⃗∗−b⃗)=0⃗A^{\mathsf{T}}(A\vec{m}^* - \vec{b}) = \vec{0}AT(Am∗−b)=0 . N(AT)\mathcal{N}(A^{\mathsf{T}})N(AT) is the orthogonal complement of C(A)\mathcal{C}(A)C(A) . Expanding gives ATAm⃗∗=ATb⃗A^{\mathsf{T}}A\vec{m}^* = A^{\mathsf{T}}\vec{b}ATAm∗=ATb .

  65. [Least squares approximate solutions] What is an affine model for data with nnn features?

    y(x⃗)=m0+m1x1+⋯+mnxn=m⃗′⋅(1,x⃗)\boldsymbol{y(\vec{x}) = m_0 + m_1 x_1 + \dots + m_n x_n = \vec{m}' \cdot (1, \vec{x})}y(x)=m0​+m1​x1​+⋯+mn​xn​=m′⋅(1,x) : a linear model plus a constant term. m⃗′=(m0,m1,…,mn)\vec{m}' = (m_0, m_1, \dots, m_n)m′=(m0​,m1​,…,mn​) ; m0m_0m0​ is the yyy -intercept.

  66. [Least squares approximate solutions] How do you fit an affine model m0+m⃗⋅x⃗m_0 + \vec{m} \cdot \vec{x}m0​+m⋅x to a dataset {A,b⃗}\{A, \vec{b}\}{A,b} with least squares?

    Add a column of ones to AAA to get A′A'A′ , then m⃗′∗=(A′TA′)−1A′Tb⃗\vec{m}'^* = (A'^{\mathsf{T}}A')^{-1}A'^{\mathsf{T}}\vec{b}m′∗=(A′TA′)−1A′Tb . Row iii of A′A'A′ is (1,a⃗i)(1, \vec{a}_i)(1,ai​) , and (1,a⃗i)⋅(m0,m⃗)=m0+m⃗⋅a⃗i(1, \vec{a}_i) \cdot (m_0, \vec{m}) = m_0 + \vec{m} \cdot \vec{a}_i(1,ai​)⋅(m0​,m)=m0​+m⋅ai​ . Adding the column is called preprocessing (data massaging).

  67. [Least squares approximate solutions] Find the best affine model y(x)=m0+m1xy(x) = m_0 + m_1 xy(x)=m0​+m1​x for the data points (105,45),(113,63),(125,86),(137,118),(141,112),(153,169)(105, 45), (113, 63), (125, 86), (137, 118), (141, 112), (153, 169)(105,45),(113,63),(125,86),(137,118),(141,112),(153,169) .

    y(x)≈−210.4+2.397x\boldsymbol{y(x) \approx -210.4 + 2.397x}y(x)≈−210.4+2.397x A′=[1105⋮⋮1153]A' = \begin{bmatrix} 1 & 105 \\ \vdots & \vdots \\ 1 & 153 \end{bmatrix}A′=⎣⎡​1⋮1​105⋮153​⎦⎤​ , and A′TA′m⃗′=A′Tb⃗A'^{\mathsf{T}}A'\vec{m}' = A'^{\mathsf{T}}\vec{b}A′TA′m′=A′Tb is [6774774101478][m0m1]=[59380409]\begin{bmatrix} 6 & 774 \\ 774 & 101478 \end{bmatrix}\begin{bmatrix} m_0 \\ m_1 \end{bmatrix} = \begin{bmatrix} 593 \\ 80409 \end{bmatrix}[6774​774101478​][m0​m1​​]=[593…

  68. [Least squares approximate solutions] Do the terms linear regression and linear least squares cover only linear models m⃗⋅x⃗\vec{m} \cdot \vec{x}m⋅x ?

    No, they also cover affine models m0+m⃗⋅x⃗m_0 + \vec{m} \cdot \vec{x}m0​+m⋅x . An affine model is a linear model in (1,x⃗)(1, \vec{x})(1,x) .

  69. [Least squares approximate solutions] How do you fit the quadratic model m0+m1x+m2y+m3xy+m4x2+m5y2m_0 + m_1 x + m_2 y + m_3 xy + m_4 x^2 + m_5 y^2m0​+m1​x+m2​y+m3​xy+m4​x2+m5​y2 to data points (xi,yi)(x_i, y_i)(xi​,yi​) with outcomes bib_ibi​ by least squares?

    Make the data matrix A′A'A′ with rows (1,xi,yi,xiyi,xi2,yi2)(1, x_i, y_i, x_i y_i, x_i^2, y_i^2)(1,xi​,yi​,xi​yi​,xi2​,yi2​) , then m⃗∗=(A′TA′)−1A′Tb⃗\vec{m}^* = (A'^{\mathsf{T}}A')^{-1}A'^{\mathsf{T}}\vec{b}m∗=(A′TA′)−1A′Tb . The model is nonlinear in (x,y)(x, y)(x,y) but linear in the parameters m⃗\vec{m}m .

  70. [Least squares approximate solutions] How many parameters does a general quadratic model in nnn variables have?

    12(n+1)(n+2)\boldsymbol{\frac{1}{2}(n+1)(n+2)}21​(n+1)(n+2) 1 constant, nnn linear terms, nnn squares and n(n−1)2\frac{n(n-1)}{2}2n(n−1)​ products xixjx_i x_jxi​xj​ ( i<ji < ji<j ).Example: n=2n = 2n=2 gives 6: 1,x,y,xy,x2,y21, x, y, xy, x^2, y^21,x,y,xy,x2,y2 .

  71. [Least squares approximate solutions] A dataset has n=1000n = 1000n=1000 features. Why fit an affine model rather than a quadratic one?

    The quadratic model has 12(1001)(1002)=501501\frac{1}{2}(1001)(1002) = 50150121​(1001)(1002)=501501 parameters, so A′TA′A&#x27;^{\mathsf{T}}A&#x27;A′TA′ is 501501×501501501501 \times 501501501501×501501 : about a terabyte to store, and very slow to invert. The affine model needs only a 1001×10011001 \times 10011001×1001 matrix A′TA′A&#x27;^{\mathsf{T}}A&#x27;A′TA′ . Linear models are powerful, easy to implement and computationally cheap.

  72. [Computer graphics] What is an affine transformation of vectors v⃗\vec{v}v ?

    A linear transformation TTT followed by a translation by a fixed vector d⃗\vec{d}d : w⃗=T(v⃗)+d⃗\ \vec{w} = T(\vec{v}) + \vec{d} w=T(v)+d . Example: T(x,y)=(2x,2y)T(x, y) = (2x, 2y)T(x,y)=(2x,2y) and d⃗=(1,0)\vec{d} = (1, 0)d=(1,0) give (3,4)↦(6,8)+(1,0)=(7,8)(3, 4) \mapsto (6, 8) + (1, 0) = (7, 8)(3,4)↦(6,8)+(1,0)=(7,8) .

  73. [Computer graphics] Why does computer graphics use homogeneous coordinates?

    They let every affine transformation w⃗=T(v⃗)+d⃗\vec{w} = T(\vec{v}) + \vec{d}w=T(v)+d (and also every perspective transformation) be written as one matrix-vector product W⃗=AV⃗\vec{W} = A\vec{V}W=AV . Translations and perspective projections are not linear in ordinary coordinates. With homogeneous coordinates the whole graphics pipeline is a sequence of matrix multiplications.

  74. [Computer graphics] What are the homogeneous coordinates of the point p=(x,y,z)c∈R3p = (x, y, z)_c \in \mathbb{R}^3p=(x,y,z)c​∈R3 (subscript ccc = cartesian coordinates)?

    P=(x,y,z,1)h∈R4\boldsymbol{P = (x, y, z, 1)_h \in \mathbb{R}^4}P=(x,y,z,1)h​∈R4 An nnn -dimensional vector becomes an (n+1)(n+1)(n+1) -dimensional vector with last component 1, and a transformation becomes an (n+1)×(n+1)(n+1) \times (n+1)(n+1)×(n+1) matrix.Example: p=(2,5)c∈R2p = (2, 5)_c \in \mathbb{R}^2p=(2,5)c​∈R2 is P=(2,5,1)hP = (2, 5, 1)_hP=(2,5,1)h​ .

  75. [Computer graphics] In homogeneous coordinates, which vectors represent the same point as (a,b,c,1)h(a, b, c, 1)_h(a,b,c,1)h​ ?

    Every nonzero multiple (αa,αb,αc,α)h(\alpha a, \alpha b, \alpha c, \alpha)_h(αa,αb,αc,α)h​ , α≠0\alpha \neq 0α=0 . Homogeneous coordinates are invariant under scaling: one point corresponds to a whole set of vectors.Example: (1,2,3,1)h=(5,10,15,5)h=(500,1000,1500,500)h(1, 2, 3, 1)_h = (5, 10, 15, 5)_h = (500, 1000, 1500, 500)_h(1,2,3,1)h​=(5,10,15,5)h​=(500,1000,1500,500)h​ .

  76. [Computer graphics] How do you convert homogeneous coordinates (X,Y,W)h(X, Y, W)_h(X,Y,W)h​ with W≠0W \neq 0W=0 to cartesian coordinates in R2\mathbb{R}^2R2 ?

    Divide by the last component: (x,y)c=(XW,YW)c\ (x, y)_c = \left(\frac{X}{W}, \frac{Y}{W}\right)_c (x,y)c​=(WX​,WY​)c​ Example: (6,4,2)h=(3,2,1)h(6, 4, 2)_h = (3, 2, 1)_h(6,4,2)h​=(3,2,1)h​ , which is the point (3,2)c(3, 2)_c(3,2)c​ .

  77. [Computer graphics] Geometrically, what does a point (a,b)∈R2(a, b) \in \mathbb{R}^2(a,b)∈R2 correspond to in homogeneous coordinates (x,y,w)(x, y, w)(x,y,w) ?

    The line through the origin of R3\mathbb{R}^3R3 through (a,b,1)(a, b, 1)(a,b,1) ; the representative (a,b,1)h(a, b, 1)_h(a,b,1)h​ is the intersection of this line with the plane w=1w = 1w=1 . All vectors α(a,b,1)\alpha(a, b, 1)α(a,b,1) on the dashed line represent the point (a,b)(a, b)(a,b) .

  78. [Computer graphics] Which points do homogeneous coordinates (x,y,z,0)h(x, y, z, 0)_h(x,y,z,0)h​ (last component 0) represent?

    Points at infinity in the direction of (x,y,z)c(x, y, z)_c(x,y,z)c​ . They cannot be divided by the last component, so they correspond to no point of R3\mathbb{R}^3R3 .

  79. [Computer graphics] The affine transformation w⃗=MTv⃗+d⃗\vec{w} = M_T \vec{v} + \vec{d}w=MT​v+d on R2\mathbb{R}^2R2 has MT=[m11m12m21m22]M_T = \begin{bmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{bmatrix}MT​=[m11​m21​​m12​m22​​] and d⃗=(d1,d2)\vec{d} = (d_1, d_2)d=(d1​,d2​) . Which 3×33 \times 33×3 matrix represents it in homogeneous coordinates?

    [m11m12d1m21m22d2001]\boldsymbol{\begin{bmatrix} m_{11} & m_{12} & d_1 \\ m_{21} & m_{22} & d_2 \\ 0 & 0 & 1 \end{bmatrix}}⎣⎡​m11​m21​0​m12​m22​0​d1​d2​1​⎦⎤​ The constant component 1 of (x,y,1)(x, y, 1)(x,y,1) multiplies the third column, which adds d1d_1d1​ and d2d_2d2​ ; the last row keeps the 1.Example: MT=IM_T = IMT​=I , d⃗=(2,3)\vec{d} = (2, 3)d=(2,3) : [102013001][111]=[341]\begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{…

  80. [Computer graphics] The most general 3×33 \times 33×3 transformation of homogeneous coordinates (x,y,w)(x, y, w)(x,y,w) in 2D is [m11m12d1m21m22d2p1p21]\begin{bmatrix} m_{11} & m_{12} & d_1 \\ m_{21} & m_{22} & d_2 \\ p_1 & p_2 & 1 \end{bmatrix}⎣⎡​m11​m21​p1​​m12​m22​p2​​d1​d2​1​⎦⎤​ . What do its three parts do?

    Top-left block [m11m12m21m22]\begin{bmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{bmatrix}[m11​m21​​m12​m22​​] A linear transformation (rotation, reflection, scaling, shear, projection). Last column (d1,d2)(d_1, d_2)(d1​,d2​) A translation by d⃗=(d1,d2)\vec{d} = (d_1, d_2)d=(d1​,d2​) . Last row (p1,p2)(p_1, p_2)(p1​,p2​) A perspective transformation.

  81. [Computer graphics] Which 3×33 \times 33×3 matrix represents, in homogeneous coordinates, the clockwise rotation RθR_\thetaRθ​ by the angle θ\thetaθ in R2\mathbb{R}^2R2 ?

    MRθ=[cos⁡θsin⁡θ0−sin⁡θcos⁡θ0001]\boldsymbol{M_{R_\theta} = \begin{bmatrix} \cos\theta & \sin\theta & 0 \\ -\sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix}}MRθ​​=⎣⎡​cosθ−sinθ0​sinθcosθ0​001​⎦⎤​ The top-left 2×22 \times 22×2 block is the 2×22 \times 22×2 matrix of the clockwise rotation; the rest leaves the constant component 1 unchanged.Example: θ=90°\theta = 90°θ=90° gives (1,0,1)↦(0,−1,1)(1, 0, 1) \mapsto (0, -1, 1)(1,0,1)↦(0,−1,1) , a quarter turn clockwise.

  82. [Computer graphics] Which 3×33 \times 33×3 homogeneous-coordinate matrices represent these linear transformations of R2\mathbb{R}^2R2 ?

    Reflection through the xxx -axis MRx=[1000−10001]M_{R_x} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \end{bmatrix}MRx​​=⎣⎡​100​0−10​001​⎦⎤​ Example: (2,3,1)↦(2,−3,1)(2, 3, 1) \mapsto (2, -3, 1)(2,3,1)↦(2,−3,1) . Scaling by sxs_xsx​ and sys_ysy​ MS=[sx000sy0001]M_S = \begin{bmatrix} s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & 1 \end{bmatrix}MS​=⎣⎡​sx​00​0sy​0​001​⎦⎤​ Example: sx=2,sy=3s_x = 2, s_y = 3sx​=2,sy​=3 : (1,1,1)↦(2,3,1)(1, 1, 1) \mapsto (2, 3, 1)(1,1,1)↦(2,3,1) . Shear along the x…

  83. [Computer graphics] Which 3×33 \times 33×3 matrix represents the translation by d⃗=(dx,dy)\vec{d} = (d_x, d_y)d=(dx​,dy​) in homogeneous coordinates?

    MTd⃗=[10dx01dy001]\boldsymbol{M_{T_{\vec{d}}} = \begin{bmatrix} 1 & 0 & d_x \\ 0 & 1 & d_y \\ 0 & 0 & 1 \end{bmatrix}}MTd​​=⎣⎡​100​010​dx​dy​1​⎦⎤​ The top-left block is the identity: no linear transformation, only the translation.Example: d⃗=(2,3)\vec{d} = (2, 3)d=(2,3) moves (1,1)(1, 1)(1,1) to (3,4)(3, 4)(3,4) .

  84. [Computer graphics] Which transformations of R2\mathbb{R}^2R2 can be written as multiplication by a 3×33 \times 33×3 matrix in homogeneous coordinates?

    Rotations, reflections, scalings, shears, projections and translations (all affine transformations), and also perspective transformations. The letter F under each 3×33 \times 33×3 matrix.

  85. [Computer graphics] In a perspective projection, where is the image of an object point seen by an observer OOO ?

    Where the light ray from the point to the eye of OOO crosses the projective plane. The side of the square closer to the observer appears longer than the farther side.

  86. [Computer graphics] The observer is at O=(0,0)O = (0, 0)O=(0,0) . Which point p′=(x′,y′)p&#x27; = (x&#x27;, y&#x27;)p′=(x′,y′) on the line y=dy = dy=d is the perspective projection of p=(x,y)p = (x, y)p=(x,y) ?

    p′=(dyx, d)\boldsymbol{p&#x27; = \left(\frac{d}{y}x, \; d\right)}p′=(yd​x,d) By similar triangles, x′x=dy\frac{x&#x27;}{x} = \frac{d}{y}xx′​=yd​ . Example: d=2d = 2d=2 , p=(3,4)p = (3, 4)p=(3,4) : p′=(24⋅3,2)=(1.5,2)p&#x27; = (\frac{2}{4} \cdot 3, 2) = (1.5, 2)p′=(42​⋅3,2)=(1.5,2) .

  87. [Computer graphics] Perspective projection onto the line y=dy = dy=d , observer at the origin: (x,y)↦(dyx, d)(x, y) \mapsto \left(\frac{d}{y}x, \; d\right)(x,y)↦(yd​x,d) .Why is this not a matrix-vector product in ordinary coordinates?

    It divides by yyy , so it is not linear in yyy . Every linear map is a matrix-vector product, and only linear maps are.

  88. [Computer graphics] Which 3×33 \times 33×3 matrix gives the perspective transformation onto the line y=dy = dy=d (observer at the origin) in homogeneous coordinates?

    [10001001d0]\boldsymbol{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & \frac{1}{d} & 0 \end{bmatrix}}⎣⎡​100​01d1​​000​⎦⎤​ , since [dyxd1]=[xyyd]\begin{bmatrix} \frac{d}{y}x \\ d \\ 1 \end{bmatrix} = \begin{bmatrix} x \\ y \\ \frac{y}{d} \end{bmatrix}⎣⎡​yd​xd1​⎦⎤​=⎣⎡​xydy​​⎦⎤​ in homogeneous coordinates. Scaling invariance moves the factor dy\frac{d}{y}yd​ out: (dyx,d,1)h=dy(x,y,yd)h(\frac{d}{y}x, d, 1)_h = \frac{d}{y}(x, y, \frac{y}{d})_h(yd​x,d,1)h​=yd​(x,y,dy​)h​ . The result is linear in xxx…

  89. [Computer graphics] Why does a third component W′≠1W&#x27; \neq 1W′=1 in an output (X′,Y′,W′)h(X&#x27;, Y&#x27;, W&#x27;)_h(X′,Y′,W′)h​ make perspective transformations possible with matrices?

    Converting to cartesian coordinates divides every component by W′W&#x27;W′ , so a W′W&#x27;W′ computed from the input coordinates gives the division that perspective needs. Example: W′=ydW&#x27; = \frac{y}{d}W′=dy​ turns (x,y)(x, y)(x,y) into (dyx,d)(\frac{d}{y}x, d)(yd​x,d) .

  90. [Computer graphics] What is a perspective projection, as opposed to a perspective transformation?

    A perspective transformation followed by an orthogonal projection that deletes some of the vector's components. Onto the line y=dy = dy=d : ΠxP=[10001d0]\Pi_x P = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \frac{1}{d} & 0 \end{bmatrix}Πx​P=[10​0d1​​00​] maps (x,y,1)(x, y, 1)(x,y,1) to (x′,1)h(x&#x27;, 1)_h(x′,1)h​ , keeping only the coordinate x′x&#x27;x′ along the line.

  91. [Computer graphics] Why does the book keep the perspective transformation PPP separate from the projection Πx\Pi_xΠx​ that deletes the y′y&#x27;y′ coordinate?

    The math is easier to understand, and the depth information (the yyy -coordinates) shows which objects appear in front of others.

  92. [Computer graphics] The observer is at the origin and n⃗=(a,b)\vec{n} = (a, b)n=(a,b) . Why is x′x=y′y=dax+by\frac{x&#x27;}{x} = \frac{y&#x27;}{y} = \frac{d}{ax + by}xx′​=yy′​=ax+byd​ for the projection p′=(x′,y′)p&#x27; = (x&#x27;, y&#x27;)p′=(x′,y′) of p=(x,y)p = (x, y)p=(x,y) onto the line ax+by=dax + by = dax+by=d ?

    By similar triangles, both ratios equal ℓ′ℓ\frac{\ell&#x27;}{\ell}ℓℓ′​ , where ℓ,ℓ′\ell, \ell&#x27;ℓ,ℓ′ are the distances of p,p′p, p&#x27;p,p′ from OOO measured along n⃗\vec{n}n . ℓ=n⃗⋅p∥n⃗∥=ax+by∥n⃗∥\ell = \frac{\vec{n} \cdot p}{\|\vec{n}\|} = \frac{ax + by}{\|\vec{n}\|}ℓ=∥n∥n⋅p​=∥n∥ax+by​ and ℓ′=n⃗⋅p′∥n⃗∥=d∥n⃗∥\ell&#x27; = \frac{\vec{n} \cdot p&#x27;}{\|\vec{n}\|} = \frac{d}{\|\vec{n}\|}ℓ′=∥n∥n⋅p′​=∥n∥d​ , since p′p&#x27;p′ lies on the line ax+by=dax + by = dax+by=d . α\alphaα and α′\alpha&#…

  93. [Computer graphics] Which 3×33 \times 33×3 matrix gives the general perspective transformation onto the line ax+by=dax + by = dax+by=d , observer at the origin?

    [100010adbd0]\boldsymbol{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ \frac{a}{d} & \frac{b}{d} & 0 \end{bmatrix}}⎣⎡​10da​​01db​​000​⎦⎤​ , so W′=adx+bdyW&#x27; = \frac{a}{d}x + \frac{b}{d}yW′=da​x+db​y . From x′=dax+byxx&#x27; = \frac{d}{ax + by}xx′=ax+byd​x and y′=dax+byyy&#x27; = \frac{d}{ax + by}yy′=ax+byd​y : (x′,y′,1)h=(x,y,ax+byd)h(x&#x27;, y&#x27;, 1)_h = (x, y, \frac{ax + by}{d})_h(x′,y′,1)h​=(x,y,dax+by​)h​ . With a=0a = 0a=0 , b=1b = 1b=1 this is the projection onto y=dy = dy=d .Example:…

  94. [Computer graphics] How are the general affine transformation and the perspective transformation onto the plane ax+by+cz=dax + by + cz = dax+by+cz=d (observer at the origin) represented in 3D homogeneous coordinates?

    By 4×44 \times 44×4 matrices: A=[m11m12m13d1m21m22m23d2m31m32m33d30001]\ \boldsymbol{A = \begin{bmatrix} m_{11} & m_{12} & m_{13} & d_1 \\ m_{21} & m_{22} & m_{23} & d_2 \\ m_{31} & m_{32} & m_{33} & d_3 \\ 0 & 0 & 0 & 1 \end{bmatrix}} A=⎣⎡​m11​m21​m31​0​m12​m22​m32​0​m13​m23​m33​0​d1​d2​d3​1​⎦⎤​ , P=[100001000010adbdcd0]\ \boldsymbol{P = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \frac{a}{d} & \frac{b}{d} & \frac{c}{d} & 0 \end{bmatrix}} P=⎣⎡​100da​​010db​​001dc​​0000​⎦…

  95. [Computer graphics] What is the main practical advantage of writing all graphics transformations as matrices in homogeneous coordinates?

    They compose by matrix multiplication: applying AAA and then BBB is multiplying by the single matrix BABABA . Example: translation TTT by (1,0)(1, 0)(1,0) , then scaling SSS by 2: ST=[202020001]ST = \begin{bmatrix} 2 & 0 & 2 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix}ST=⎣⎡​200​020​201​⎦⎤​ maps (1,1,1)(1, 1, 1)(1,1,1) to (4,2,1)(4, 2, 1)(4,2,1) , as TTT gives (2,1)(2, 1)(2,1) and SSS gives (4,2)(4, 2)(4,2) .

  96. [Computer graphics] The processor dedicated to graphics operations is the graphics processing unit (GPU); its thousands of individual processing units are called shaders.

    Drawing a 3D scene (rendering) means doing linear algebra on the many polygons of the 3D models: translating, rotating and scaling them into the scene, then projecting onto the 2D window.

  97. [Computer graphics] Which three matrices make up the graphics processing pipeline, and what does each do?

    Model matrix MMM From object space (a coordinate system centred on the object) to world space: positions the object in the scene. View matrix VVV From world space to camera space: positions the camera in the scene. Projection matrix Πs\Pi_sΠs​ From camera space to screen space: computes what appears on the screen.

  98. [Computer graphics] Graphics pipeline: model matrix MMM , view matrix VVV , projection matrix Πs\Pi_sΠs​ . A vertex (x,y,z,1)m(x, y, z, 1)_m(x,y,z,1)m​ goes to the pixel coordinates (x′,y′)s=ΠsVM(x,y,z,1)m(x&#x27;, y&#x27;)_s = \Pi_s V M (x, y, z, 1)_m(x′,y′)s​=Πs​VM(x,y,z,1)m​ .Why compute C=ΠsVMC = \Pi_s V MC=Πs​VM once instead of three matrix-vector products per vertex?

    Then each vertex needs only one matrix-vector product C(x,y,z,1)C(x, y, z, 1)C(x,y,z,1) . For another object only MMM changes; VVV and Πs\Pi_sΠs​ stay the same.

  99. [Computer graphics] Graphics pipeline: (x′,y′)s=ΠsVM(x,y,z,1)m(x&#x27;, y&#x27;)_s = \Pi_s V M (x, y, z, 1)_m(x′,y′)s​=Πs​VM(x,y,z,1)m​ with model matrix MMM , view matrix VVV , projection matrix Πs\Pi_sΠs​ .How is this written in the customary transpose picture, where data flows from left to right?

    (x,y,z,1)mMTVTΠsT=(x′,y′)s\boldsymbol{(x, y, z, 1)_m M^{\mathsf{T}} V^{\mathsf{T}} \Pi_s^{\mathsf{T}} = (x&#x27;, y&#x27;)_s}(x,y,z,1)m​MTVTΠsT​=(x′,y′)s​ Vectors are row vectors, and (ΠsVMv⃗)T=v⃗TMTVTΠsT(\Pi_s V M \vec{v})^{\mathsf{T}} = \vec{v}^{\mathsf{T}} M^{\mathsf{T}} V^{\mathsf{T}} \Pi_s^{\mathsf{T}}(Πs​VMv)T=vTMTVTΠsT​ . Combined matrix: CT=MTVTΠsTC^{\mathsf{T}} = M^{\mathsf{T}} V^{\mathsf{T}} \Pi_s^{\mathsf{T}}CT=MTVTΠsT​ .

  100. [Computer graphics] What are the two graphics pipelines in a GPU?

    The geometry pipeline transforms the polygons of the 3D objects; the texture pipeline controls the pattern the polygons are filled with. The last rendering step combines the outputs of both.