Chiemi Kato - Projects

Tropical Root Systems, Polytopes of dimensions n

An Introduction

This page is dedicated to introducing a few of the underlying concepts around tropical surfaces, and our research work around the spectra of four types of these surfaces. The goal for this website is to share some of the code implementations in Python, and to look at these algorithms within the context of the research at hand. All research was completed by Federico Ardila, Isabel Perez, Jewell McMillon, and Chiemi Kato of San Francisco State University.

Background

Farhad Babaee and June Huh (2017) introduced the tropical Laplacian of a tropical surface. From our research, we have constructed four families of tropical surfaces arising from root polytopes. From there, we computed their spectra, confirming that they have exactly one negative eigenvalue, as anticipated by Babaee and Huh.

Some Definitions

A \(\color{green}{\text{polytope}}\) P is the convex hull of finitely many points \(V=\{v_1, \dots, v_n\}\) in \(\mathbb{R}^d\).
We say \(P\) is \(\color{green}{\text{balanced}}\) if for each vertex \(v\in V\), there exists \(c_v \in \mathbb{R}\) such that \[\sum_ {w \sim v} w = c_vv.\]
Let \(P\) be a balanced polytope. The \(\color{green}{\text{tropical Laplacian}}\) \(TL(P)\) is a symmetric \(V \times V\) matrix given by \[TL(P)_{v,w} =\begin{cases} c_v &\text{ if } v= w\\ -1 &\text{ if } v \sim w\\ 0 &\text{ otherwise. } \end{cases}\]
The \(\color{green}{\text{spectrum}}\) of a square matrix \(A\) is the set of its eigenvalues.

Example

Let \(e_i\) be the \(i^{th}\) basis vector.

\(A_2\) is the convex hull of \(\{e_i-e_j : 1 \leq i \neq j \leq 3\}\)
\(A_2\) is balanced with \(c_v =1\).
The tropical Laplacian is given by

\[TL(P)_{v,w }=\begin{cases} 1 &\text{ if } v= w\\ -1 &\text{ if } v \sim w\\ 0 &\text{ otherwise. } \end{cases}\]

Tropical Laplacian of the Root Polytope \(A_{n-1}\)

\(\color{blue}{\text{Definition:}}\)The \((n-1)\)-dimensional \(\color{green}{\text{type A root system polytope}}\) \(A_{n-1}\) is the convex hull of \[\{e_i-e_j : 1\leq i \neq j \leq n\}.\]

\(\color{blue}{\text{Proposition:}}\) The root polytope \(A_{n-1}\) is balanced. The \(\color{green}{\text{Tropical Laplacian}}\) of \(A_{n-1}\) is given by \[ TL(A_{n-1})_{ij,k\ell}= \begin{cases} n-2 & \text{ if } i=k \text{ and } j=\ell\\ -1 & \text{ if } i=k \text{ and } j\neq \ell \text{ or } j\neq k \text{ and } j=\ell\\ 0& \text{ otherwise. } \end{cases} \]

This is the polytope \(A_3\). (\(e_i-e_j\) which is denoted by \(ij\))

Theorem

The \(\color{green}{\text{spectrum}}\) of \(TL(A_{n-1})\) is

\(2-n,\;\underbrace{0, \cdots, 0}_{n-1},\; \underbrace{2, \cdots, 2}_{n-1},\; \underbrace{n ,\dots, n}_{n^2-3n+1}.\)

In particular, \(TL(A_{n-1})\) has exactly one negative eigenvalue.

Spectra of the Tropical Polytope \(A_{n-1}\)

The following code demonstrates that our theorem is correct. For inputted n dimension values of 3 and 5, we get the correct eigenvalues and multiplicities.

First we will install the following modules for later use.

import itertools as it
import numpy as np
np.set_printoptions(threshold=np.inf)
np.set_printoptions(linewidth=2000)    # default = 75

import math
from fractions import Fraction

from numpy.linalg import matrix_rank

Next we will set the n dimension to 3 here. The other example will set n to be 5, but n can be any positive number.

n = 3
A = list(range(1,n+1))

s = list(it.permutations(A,2))

print('List of vertices : ',s)

## ('List of vertices : ', [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)])

To Build a Tropical Laplacian

We first build a matrix of nxn dimensions. Then we fill out the diagonal entries with the balance value, which is n-2 for any \(A_n\) shape.


M = np.zeros((len(s),len(s)))

for i,item in enumerate(s):
    # Here we will establish an edge between any two points who meet the following condition (as described in above proposition)

    for j,m in enumerate(s):
        if (m != item) and (m[0] == item[0] or m[1] == item[1]):
            M[i,j] = -1
        elif (i==j):
            M[i,i] = (len(A)-2)

print(M)

## [[ 1. -1.  0.  0.  0. -1.]
##  [-1.  1.  0. -1.  0.  0.]
##  [ 0.  0.  1. -1. -1.  0.]
##  [ 0. -1. -1.  1.  0.  0.]
##  [ 0.  0. -1.  0.  1. -1.]
##  [-1.  0.  0.  0. -1.  1.]]

M is the Tropical Laplacian matrix. Next we will compute the eigenvalues and multiplicities of of the Tropical Laplacian, using Python’s NumPy module (my fave).

eigVal, eigVect = np.linalg.eig(M)

for i,eig in enumerate(eigVal):
    eigVal[i] = round(eig,4)

eigVal = eigVal.tolist()

print("Tropical Laplacian Eigenvalues of A", n, ":")

## ('Tropical Laplacian Eigenvalues of A', 3, ':')

for item in sorted(set(eigVal)):
    print((item, eigVal.count(item)))

## (-1.0, 1)
## (-0.0, 2)
## (2.0, 2)
## (3.0, 1)

What Do These Results Even Mean?

By looking at these eigenvalues above, we can see that our theorem described above is true for the tropical laplacian of root polytope \(A_3\). As we can see, there are four eigenvalues. There are exactly \(n-1=3-1=2\) eigenvalues of 0 and 2, while there are \(n^2-3n+1=3^2-3*3+1=1\) eigenvalue \(n=3\) and exactly 1 negative eigenvalue of \(2-n=-1\).

Let’s take a look at the Tropical Laplacians of dimensions 5.

n = 5
A = list(range(1,n+1))

s = list(it.permutations(A,2))

print('List of vertices : ',s)

## ('List of vertices : ', [(1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4)])

M = np.zeros((len(s),len(s)))

for i,item in enumerate(s):
    # Here we will establish an edge between any two points who meet the following condition (as described in above proposition)

    for j,m in enumerate(s):
        if (m != item) and (m[0] == item[0] or m[1] == item[1]):
            M[i,j] = -1
        elif (i==j):
            M[i,i] = (len(A)-2)

print(M)

## [[ 3. -1. -1. -1.  0.  0.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.]
##  [-1.  3. -1. -1.  0. -1.  0.  0.  0.  0.  0.  0.  0.  0. -1.  0.  0.  0. -1.  0.]
##  [-1. -1.  3. -1.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0.  0.  0.  0.  0.  0. -1.]
##  [-1. -1. -1.  3.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0.  0.]
##  [ 0.  0.  0.  0.  3. -1. -1. -1. -1.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0.]
##  [ 0. -1.  0.  0. -1.  3. -1. -1.  0.  0.  0.  0.  0.  0. -1.  0.  0.  0. -1.  0.]
##  [ 0.  0. -1.  0. -1. -1.  3. -1.  0.  0. -1.  0.  0.  0.  0.  0.  0.  0.  0. -1.]
##  [ 0.  0.  0. -1. -1. -1. -1.  3.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0.  0.]
##  [ 0.  0.  0.  0. -1.  0.  0.  0.  3. -1. -1. -1. -1.  0.  0.  0. -1.  0.  0.  0.]
##  [-1.  0.  0.  0.  0.  0.  0.  0. -1.  3. -1. -1.  0. -1.  0.  0.  0. -1.  0.  0.]
##  [ 0.  0. -1.  0.  0.  0. -1.  0. -1. -1.  3. -1.  0.  0.  0.  0.  0.  0.  0. -1.]
##  [ 0.  0.  0. -1.  0.  0.  0. -1. -1. -1. -1.  3.  0.  0.  0. -1.  0.  0.  0.  0.]
##  [ 0.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0.  3. -1. -1. -1. -1.  0.  0.  0.]
##  [-1.  0.  0.  0.  0.  0.  0.  0.  0. -1.  0.  0. -1.  3. -1. -1.  0. -1.  0.  0.]
##  [ 0. -1.  0.  0.  0. -1.  0.  0.  0.  0.  0.  0. -1. -1.  3. -1.  0.  0. -1.  0.]
##  [ 0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0. -1. -1. -1. -1.  3.  0.  0.  0.  0.]
##  [ 0.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0.  3. -1. -1. -1.]
##  [-1.  0.  0.  0.  0.  0.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0. -1.  3. -1. -1.]
##  [ 0. -1.  0.  0.  0. -1.  0.  0.  0.  0.  0.  0.  0.  0. -1.  0. -1. -1.  3. -1.]
##  [ 0.  0. -1.  0.  0.  0. -1.  0.  0.  0. -1.  0.  0.  0.  0.  0. -1. -1. -1.  3.]]

eigVal, eigVect = np.linalg.eig(M)
eigVal = eigVal.tolist()

for i,eig in enumerate(eigVal):
    eigVal[i] = round(eigVal[i].real,4)
    eigVal[i] = eigVal[i].real


print("Tropical Laplacian Eigenvalues of A", n, ":")

## ('Tropical Laplacian Eigenvalues of A', 5, ':')

for item in sorted(set(eigVal)):
    print((item, eigVal.count(item)))

## (-3.0, 1)
## (-0.0, 4)
## (2.0, 4)
## (5.0, 11)

Again, we get four eigenvalues for the Tropical Laplacian of dimension n=5. Just like the previous example, the multiplicities of each of these eigenvalues match those listed in the theorem above. Specifically, there are \(n-1=5-1=4\) eigenvalues of 0 and 2, and \(n^2-3n+1=5^2-3*5+1=11\) eigenvalues of 5 and exactly 1 negative eigenvalue of \(2-n=-3\).

A New Way to Visualize Eigenvectors

Let \(\stackrel{\leftrightarrow}{K_{n}}\) be a complete directed graph on \(n\) vertices with edges corresponding to the vertices of \(A_{n-1}\). In particular, the edge that has vertex \(i\) as a source and a vertex \(j\) as a sink corresponds to the vertex \(e_i -e_j\).

For Example

The graph of \(\stackrel{\leftrightarrow}{K_{2}}\)

The graph of \(\stackrel{\leftrightarrow}{K_{3}}\)

Eigenvectors of \(TL(A_{n-1})\)

Eigenvectors of \(TL(A_{n-1})_{ij,k\ell}\) can be represented by weighted subgraphs of \(\stackrel{\leftrightarrow}{K_{n}}\).

Tropical Root Polytopes