Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Graph laplacian — the series

3 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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 in these essays whose kernel is known before anything runs.

    part 1 · graph
  2. 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

    The combinatorial Laplacian D − A and the normalised one, which conjugates it by the inverse square roots of the degrees, 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.

    part 2 · graph
  3. 1611162126110¹10²10³degree of the grounded vertexcondition number of what is left1, the best choicea parameter nobody setsvertices tried30best κ1at degree29worst κ898at degree1spread898one row and column deletedand it matters which

    The vertex nobody solves for

    A Laplacian is singular, so every solve with one has to remove its kernel first. There are three ways, they agree to fourteen digits, and the one everybody uses carries a free parameter that no account of the method mentions and that moves the condition number by nine hundred.

    part 3 · graph

All series