Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Quadratic form — where it appears

The scalar x^T A x, read as a function of the vector rather than of the matrix. For a graph Laplacian it is a sum over edges of squared differences, so it is a statement about the graph, and it is what a sparsifier and a partition are both defined by.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

the matrix, measuredvertices40edges223‖L·1‖∞0zero eigenvalues1components, by search1λ₂1.5laid out at its own eigenvectorsand the row sums are exactly zero

A matrix with no numbers in it

A graph arrives as vertices and edges. Two different matrices can be built from it, they answer different questions, and one of them has a null vector that is exact — the only object on this site whose kernel is known before anything runs.

graph · graph laplacian 10⁻³10⁻²10⁻¹110¹12345678910conductance, and the two bounds on itpathcyclegridbarbelltwo blockshypercubepreferentialstarcompletethe bar is the inequalitythe dot is the graph

Two Laplacians of one graph

D − A and D^{-1/2}(D − A)D^{-1/2} are built from the same object, are not similar to each other, and answer different questions. On a graph whose degrees are equal they coincide. On one whose degrees span an order of magnitude their second eigenvalues are sixteen times apart.

graph · graph laplacian 19172533414911.251.51.752indexsample ÷ originalkept, and not keptedges kept344of1225eigenvalue ratio, low0.43high1.7degree ratio, low0.56high1.5diameter, after3filled dots are eigenvaluesopen dots are degrees

A graph with a tenth of the edges

Keeping 344 of 1,225 edges, sampled by effective resistance and reweighted, preserves every eigenvalue of the Laplacian to within a factor of 1.7. It preserves no degree — half of them are wrong by more than a third — and it takes the diameter from one to three.

graph · effective resistance

Named alongside it

The objects these essays reach for when they reach for this one.

Graph laplacianAlgebraic connectivityDegree sequenceAdjacency matrixConductanceConnected componentsDiagonal scalingEffective resistanceExact ground truthFoster theoremImportance samplingNormalised laplacian

All concepts