Featured Post

9444

The Miracle of Integer Eigenvalues is a paper that shows how any partially-ordered set can be used to generate a matrix with integer eigenvalues.

R. Kenyon et al, Funct. Anal. Its Appl. 58, 182–194 (2024)  doi: 10.1134/S0016266324020072, arXiv:2401.05291v2

Here I outline the process and give two examples.

restart

PartiallyOrderedSets is after GraphTheory so its DrawGraph gets priority.

with(GraphTheory); with(LinearAlgebra); with(PartiallyOrderedSets)

Example (the first example in the paper): Poset in 3 elements with one relation {u < v, {u, v, w}}.

vars := [u, v, w]; n := nops(vars); rels := {u < v}

[u, v, w]

3

{u < v}

Some derived things we will need.

translate := `~`[`=`](vars, [`$`(1 .. n)]); arcs := map(`@`(`[]`, op), rels); A := AdjacencyMatrix(Graph(vars, arcs))

translate := [u = 1, v = 2, w = 3]

arcs := {[u, v]}

Matrix(%id = 36893490746138016812)

p := PartiallyOrderedSet(vars, A)

module PosetObject () local numElems::':-integer', height::':-integer', width::':-integer', comparator::procedure, comparatorExists::boolean, transitiveClosure::Matrix, transitiveClosureExists::boolean, transitiveReduction::Matrix, transitiveReductionExists::boolean, elementMap::table, minimalElements::set, minimalElementsExists::boolean, leastElement::':-integer', maximalElements::set, maximalElementsExists::boolean, greatestElement::':-integer', closureGraph::Graph, closureGraphExists::boolean, connectedComponents::(set(set)), connectedComponentsExists::boolean, reductionGraph::Graph, reductionGraphExists::boolean, adjList::Array, adjListExists::boolean, isLattice::boolean, isFaceLattice::boolean, grade::':-integer', isGraded::boolean, isRanked::boolean, rankFuction::procedure, rankTable::Array, rankFuctionExists::boolean; option object; end module

We can represent this as a directed graph.

DrawGraph(p, size = [200, 200])

There are three linear extensions; roughly these are linear orders/chains with all of {u, v, w} that maintain u < v. In this case there are three: u < v and v < w, u < w and w < v, w < u and u < v. In other words, we want to find all permutations of [1,2,3] in which 1 (=u) precedes 2 (=v). We can use the iterator TopologicalSorts, which finds all permutations satisfying some relations.

T := Iterator:-TopologicalSorts(n, subs(translate, rels))

_m2598758943744

The three permutations that have u before v are given below both numerically and symbolically.

extnums := [seq([seq(t)], `in`(t, T))]; exts := [seq(vars[[seq(t)]], `in`(t, T))]

[[1, 2, 3], [1, 3, 2], [3, 1, 2]]

[[u, v, w], [u, w, v], [w, u, v]]

Choose two of these, P and Q, say the first two.

Pnum, Qnum := extnums[1 .. 2][]; P, Q := exts[1 .. 2][]

[1, 2, 3], [1, 3, 2]

[u, v, w], [u, w, v]

Then the kth node in Q is a (P,Q) disagreement node or descent node if the k-1th node in Q is greater than the kth node, considered as a relation in P.  For example, for k = 2 (w in Q), so k-1 = 1 (u in Q) then in P we have u < w and w is a (P,Q) agreement node. For k = 3 (v) and k-1 = 2 (w) we have w > v in P and disagreement. The first node in Q is defined to be an agreement node. So u = agree, w = agree, v = disagree. We make a list of agreements (0) and disagreements (1) from k = 2 to k = n and find [0,1].

As a procedure we have

eps := proc(P::permlist, Q::permlist)
local k, i, j, L;
for k from 2 to nops(Q) do
  member(Q[k-1], P, 'i');
  member(Q[k], P, 'j');
  if i < j then L[k] := 0 else L[k] := 1 end if;
end do;
convert(L, list);
end proc:

eps(Pnum, Qnum)

[0, 1]

So now we do this for all P,Q pairs and fill a 3x3 matrix with a variable indexed with the generated lists

M := Matrix(nops(extnums), proc (i, j) options operator, arrow; index(a, eps(extnums[i], extnums[j])[]) end proc)

:=

And we find this matrix has eigenvalues that are linear combinations of these variables, with integer coefficients

Eigenvalues(M, output = list)

[a[0, 0]-a[1, 0], a[0, 0]-a[0, 1], a[0, 0]+a[1, 0]+a[0, 1]]

And of course if these variables had integer values, the matrix would have all integer eigenvalues.

inds := indets(M); r := rand(-20 .. 20); M2 := eval(M, `~`[`=`](inds, {seq(r(), 1 .. nops(inds))})); Eigenvalues(M2, output = list)

M2 :=

[7, -7, -6]

Example 2: A poset with the Hasse diagram: (generated below)

It is convenient to enter only the arcs shown (not b<e)

vars := [a, b, c, d, e]; n := nops(vars); rels := {a < c, b < c, b < d, d < e}

[a, b, c, d, e]

5

{a < c, b < c, b < d, d < e}

Specify input = transitivereduction so the missing relation doesn't throw an error.

translate := `~`[`=`](vars, [`$`(1 .. n)]); arcs := map(`@`(`[]`, op), rels); A := AdjacencyMatrix(Graph(vars, arcs)); p := PartiallyOrderedSet(vars, A, input = transitivereduction)

translate := [a = 1, b = 2, c = 3, d = 4, e = 5]

arcs := {[a, c], [b, c], [b, d], [d, e]}

Matrix(%id = 36893490746159485164)

module PosetObject () local numElems::':-integer', height::':-integer', width::':-integer', comparator::procedure, comparatorExists::boolean, transitiveClosure::Matrix, transitiveClosureExists::boolean, transitiveReduction::Matrix, transitiveReductionExists::boolean, elementMap::table, minimalElements::set, minimalElementsExists::boolean, leastElement::':-integer', maximalElements::set, maximalElementsExists::boolean, greatestElement::':-integer', closureGraph::Graph, closureGraphExists::boolean, connectedComponents::(set(set)), connectedComponentsExists::boolean, reductionGraph::Graph, reductionGraphExists::boolean, adjList::Array, adjListExists::boolean, isLattice::boolean, isFaceLattice::boolean, grade::':-integer', isGraded::boolean, isRanked::boolean, rankFuction::procedure, rankTable::Array, rankFuctionExists::boolean; option object; end module

The graph is the transitive reduction (Hasse diagram).

DrawGraph(p, size = [200, 200])

Update the relations to include all those in the transitive closure (including b<e)

Edges(ToGraph(p, reduction = false)); rels := map(`@`(`<`, op), %)

{[a, c], [b, c], [b, d], [b, e], [d, e]}

{a < c, b < c, b < d, b < e, d < e}

Find the 9 linear extensions

T := Iterator:-TopologicalSorts(n, subs(translate, rels)); extnums := [seq([seq(t)], `in`(t, T))]; exts := [seq(vars[[seq(t)]], `in`(t, T))]

_m2598743159552

[[1, 2, 3, 4, 5], [1, 2, 4, 3, 5], [1, 2, 4, 5, 3], [2, 1, 3, 4, 5], [2, 1, 4, 3, 5], [2, 1, 4, 5, 3], [2, 4, 1, 3, 5], [2, 4, 1, 5, 3], [2, 4, 5, 1, 3]]

[[a, b, c, d, e], [a, b, d, c, e], [a, b, d, e, c], [b, a, c, d, e], [b, a, d, c, e], [b, a, d, e, c], [b, d, a, c, e], [b, d, a, e, c], [b, d, e, a, c]]

Leading to the matrix

M := Matrix(nops(extnums), proc (i, j) options operator, arrow; index(a, eps(extnums[i], extnums[j])[]) end proc)

Matrix(%id = 36893490746138048980)

The eigenvalues

Eigenvalues(M, output = list)

[a[0, 0, 0, 0]-a[0, 0, 1, 0], a[0, 0, 0, 0]-a[0, 0, 1, 0]-a[1, 0, 0, 0]+a[1, 0, 1, 0], a[0, 0, 0, 0]-a[0, 0, 1, 0]+a[1, 0, 0, 0]-a[1, 0, 1, 0], a[0, 0, 0, 0]-a[0, 0, 0, 1]-a[1, 0, 0, 0]+a[1, 0, 0, 1], a[0, 0, 0, 0]-a[0, 0, 0, 1]-a[0, 1, 0, 0]+a[0, 1, 0, 1], a[0, 0, 0, 0]+a[0, 0, 0, 1]-a[0, 1, 0, 0]-a[0, 1, 0, 1], a[0, 0, 0, 0]-a[0, 0, 0, 1]+a[0, 1, 0, 0]-a[0, 1, 0, 1]+a[1, 0, 0, 0]-a[1, 0, 0, 1], a[0, 0, 0, 0]+a[0, 0, 0, 1]+a[0, 0, 1, 0]-a[1, 0, 0, 0]-a[1, 0, 0, 1]-a[1, 0, 1, 0], a[0, 0, 0, 0]+a[0, 0, 0, 1]+2*a[0, 0, 1, 0]+a[0, 1, 0, 0]+a[0, 1, 0, 1]+a[1, 0, 0, 0]+a[1, 0, 0, 1]+a[1, 0, 1, 0]]

and with some integer entries

inds := indets(M); M2 := eval(M, `~`[`=`](inds, {seq(r(), 1 .. nops(inds))})); Eigenvalues(M2, output = list)

M2 :=

[0, -68, -32, 3, -12, 8, -8, -6, -2]

NULL

IntegerEigenvalues.mw

 

Featured Post

Suppose you place two points on the x-y plane and ask a seemingly simple question: What is the shortest path connecting them?

The "obvious" answer is a straight line (the green curve), but how can we show that this is truly the optimal path? Imagine two fixed points (x1,y1) and (x2,y2) connected by some curve y(x).

To find the length of this curve, we zoom in on an infinitesimally small segment. If the curve changes by small amounts dx horizontally and dy vertically, then the Pythagorean theorem gives the tiny arclength ds:

Here, y' = dy/dx is the derivative/slope of y(x) with respect to x. The total length S of the curve, often referred to as the "action", is found by integrating these arclengths:

Notice that, unlike ordinary functions that take numbers as inputs, S[y] takes an entire curve y(x) as input and outputs a single number, S. Such a function is called a functional.

Our goal is to find the curve y(x) that minimizes the length S[y]. Instead of asking how the function (or "functional") S[y] changes for some change in x, we must ask how the total path length changes if we slightly deform the curve y(x) itself. This is the central idea behind a branch of calculus called "Calculus of Variations".

Let's predict that the shortest path between two curves is y(x). Without knowing that y(x) is a straight line (we haven't proved this yet!), our first prediction is probably incorrect. So, let's say the true ideal path is a nearby path y(x) + ε*η(x), where η(x) is the shape of the function that corrects our original prediction, and ε scales this correction function (i.e. controls how large the deformation is). To ensure that the endpoints remain the same, we require η(x1) = η(x2) = 0.

Substituting this new path into the expression for S[y] above, we get the path length S as a function of ε:

Notice that if ε = 0, we recover the original path y(x). If the original path does minimize S, then S has a minimum at ε = 0. That is,

So, to find the minimizing curve y(x), we find a curve y(x) such that dS/dε = 0 at ε = 0. Bringing the derivative inside of the integral for S[y] and using the chain rule, this means:

We can integrate this by parts using the substitutions:

Since we originally defined η(x1) = η(x2) = 0, the first term on the right disappears. We're left with:

Now, this must be true for any η(x) we choose, meaning:

Squaring both sides and rearranging to solve for y', we get that:

Hence, y(x) has a constant slope and is therefore a straight line. Note that there are multiple ways to prove that the shortest path between two points is a straight line (such as using the Triangle Inequality or algebraic arguments under Euclidean geometry), but this method of using least action has proven to have much deeper physical significance to more sophisticated questions, as discussed below.

As many of you have probably noticed, this argument only holds in flat Euclidean space (the space most of us are used to, like the xyz plane). In curved spaces, the analogue of a straight line is called a geodesic.

The general idea is still the same, but the formula for distance changes depending on the geometry of the space.

For example, consider the surface of the Earth. If you want the shortest route from Toronto to London while remaining on Earth's surface, you don't follow what looks like a straight line on a flat map. You follow part of a "great circle".

On a sphere of radius R, for example, the infinitesimal distance is given using spherical coordinates:

So instead of minimizing the flat-space length

we minimize:

Applying the same calculus-of-variations machinery gives the geodesics of the sphere, which turn out to be great circles.

This becomes especially interesting in general relativity. Spacetime itself is curved, and free-falling objects follow geodesics through that curved spacetime. In that sense, Earth's orbit around the Sun can be thought of not as Earth being forced away from a straight path, but as Earth following the natural geodesic of curved spacetime.

What we proved above is a remarkable fact, as the idea of minimizing the "action" functional is a fundamental characteristic of systems in nature. Instead of minimizing distance, physical systems obey the same mathematics to minimize quantities involving energy and time. For example, a hanging rope will form a shape called a catenary (a type of hyperbolic cosine function) to minimize its gravitational potential energy, not a parabola (which approximates the motion of projectiles) as one might think.

Similarly, light bends when moving between materials like air and water to minimize travel time.

So, never doubt the power of seemingly "simple" or intuitive mathematical results, as this elementary question of minimizing distance between two points uses the same mathematics that governs planetary motion, quantum fields, and spacetime itself!