Unit 12: Applications — Graphs, Data, and Computer Graphics
Where all of it lands: circuits and networks as linear systems, data compressed by its dominant directions, and shapes moved by matrices.
9 topics · 33 questions
Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.
Graphs and Incidence Matrices
- How it worksHow does each row of an incidence matrix record one edge by marking where it starts and where it ends?
- Worked exampleFind the incidence matrix for a graph with edges from node 1 to node 2 and from node 2 to node 3.
- Common mistakeWhy is a graph's incidence matrix rectangular rather than square, with one row per edge?
- Going furtherWhat happens to an incidence matrix once the graph it describes has more than one disconnected piece?
Your turn1 of 2
A graph has 8 nodes and 11 edges. Find the total number of entries (rows times columns) in its incidence matrix.The Null Space of an Incidence Matrix
- How it worksHow does a vector of potentials at every node that solves Ax = 0 correspond to no current flowing anywhere?
- Worked exampleFind the null space of the incidence matrix for a triangle graph connecting three nodes.
- Ties togetherHow does the rank of a graph's incidence matrix relate to the number of independent loops in the graph?
Your turn1 of 2
A connected graph has 5 nodes and 12 edges. Its incidence matrix has rank n - 1. Find the number of independent loops in the graph (the dimension of its cycle space).Kirchhoff's Laws as a Linear System
- How it worksHow do the incidence matrix, a diagonal matrix of conductances, and Kirchhoff's laws combine into one linear system?
- Worked exampleFind the linear system for the currents in a simple circuit with two resistors in series and one voltage source.
- Common mistakeWhy doesn't solving a circuit with linear algebra require guessing the direction of every current in advance?
- Going furtherWhat happens to the linear system once a circuit has a loop with no resistor anywhere in it?
Your turn1 of 2
A circuit has two resistors in series with resistances 14 and 13 ohms, driven by a voltage source of 22 volts. Find the current using Kirchhoff's laws.Computer Graphics and 2D Transformations
- How it worksHow does a graphics engine apply a matrix to every vertex of a shape to move the whole shape at once?
- Worked exampleFind the new coordinates of the point (2, 1) after scaling by 3 in x and 2 in y.
- Going furtherWhat happens to a shape's coordinates when a scaling matrix is applied and then a rotation, versus the other order?
- Common mistakeWhy doesn't scaling a shape by a negative number in graphics just shrink it, when it flips the shape over too?
Your turn1 of 2
Find the new x-coordinate of the point (4, 3) after scaling by 5 in x and -3 in y.Homogeneous Coordinates and Translation
- How it worksHow does adding an extra coordinate along with an extra row and column let translation join the linear transformations?
- Worked exampleFind the homogeneous transformation matrix that translates every point by (3, 2).
- Common mistakeWhy isn't translation actually a linear transformation on the original 2D coordinates?
- Going furtherWhat happens when a translation is combined with a rotation using homogeneous coordinates, in each possible order?
Your turn1 of 2
The homogeneous transformation matrix that translates by (4, 3) is applied to the point (8, -4). Find the resulting x-coordinate.3D Rotations in Computer Graphics
- How it worksHow does a 3D rotation matrix around the z-axis leave the z-coordinate completely untouched?
- Worked exampleFind the matrix that rotates points 90 degrees around the z-axis in 3D.
- Going furtherWhat happens when a rotation around the x-axis is combined with a rotation around the y-axis?
Your turn1 of 2
A point (4, 3, 8) is rotated around the z-axis by 1.68 radians. Find the resulting x-coordinate.Principal Component Analysis
- How it worksHow do the eigenvectors of a data set's covariance matrix point along the directions of greatest spread?
- Worked exampleFind the direction of greatest variance for a data set whose covariance matrix is [[4, 2], [2, 1]].
- Common mistakeWhy doesn't the first principal component have to line up with one of the original measured variables?
- Ties togetherHow does computing principal components using the SVD avoid ever forming the covariance matrix directly?
Your turn1 of 2
Find the largest eigenvalue of the covariance matrix [[7, 3], [3, 9]] — the variance captured along the first principal component.Image Compression with Low-Rank Approximation
- How it worksHow does keeping only the largest singular values of an image's matrix throw away the least important visual detail first?
- Worked exampleFind how much storage is saved when a 100 by 100 image matrix is approximated using only its top 5 singular values.
- Going furtherWhat happens to a compressed image's quality as more and more singular values get kept?
Your turn1 of 2
Find how much storage is saved (in numbers) when a 145 by 145 image matrix is approximated using only its top 7 singular values, compared to storing all n2 entries. Use 2nk + k as the storage cost of the approximation.Eigenvector Centrality and PageRank
- How it worksHow does turning the web's links into a giant Markov matrix let its steady-state eigenvector rank every page at once?
- Worked exampleFind the ranking of three pages in a tiny network where page A links to B and C, page B links to C, and page C links to A.
- Common mistakeWhy doesn't a page with more incoming links always outrank a page with fewer but far more important ones?
- Ties togetherHow does PageRank tie together eigenvectors, Markov matrices, and steady states into one real piece of software everyone uses?
Your turn1 of 2
In a network, page A's PageRank score is the sum of the scores of pages linking to it, each divided by how many outbound links that page has. Pages B and C link to A; B has 4 outbound links and score 0.939, and C has 4 outbound links and score 0.351. Find A's score (before normalization).