2021-06-18

トロピカル代数でグラフの最短距離計算、トロピカル行列式、トロピカル版代数学の基本定理、トロピカルPCA

論文Tropical Principal Component Analysis and its Application to Phylogenetics https://arxiv.org/pdf/1710.02682.pdf

トロピカル演算と行列のトロピカル積とトロピカル行列式とグラフの最短距離計算

トロピカル演算 $x \oplus y = min(x,y)$ , $x \otimes y = x + y$ がある
行列の積にも同じように定義する
今、グラフの距離行列 A を作る。ただし、対角成分は0とし、エッジのない頂点ペアに対応するセルは無限大とする
このとき、頂点数nに対して、 $A^{\otimes n-1}$ (行列Aのトロピカル積のn-1回繰り返し)は、頂点ペア間の最短距離になると言う
Rで確かめる

# トロピカル演算の関数を作る
my.tropical.sum <- function(x,y=NULL){
  min(c(x,y))
}
my.tropical.prod <- function(x,y){
  x+y
}
# トロピカル行列積の関数を作る
my.tropical.matrix.prod <- function(X,Y){
  ret <- matrix(0,length(X[,1]),length(Y[1,]))
  
  for(i in 1:length(X[,1])){
    for(j in 1:length(Y[1,])){
      tmp <- c()
      for(k in 1:length(X[1,])){
        tmp   <- c(tmp,my.tropical.prod(X[i,k],Y[k,j]))
      }
      ret[i,j] <- my.tropical.sum(tmp)
    }
  }
  return(ret)
}
# 関数の検算
x <- 3
y <- 5
my.tropical.sum(x,y)
my.tropical.sum(c(x,y)) 
my.tropical.prod(x,y)

my.tropical.sum(Inf,3)
my.tropical.prod(Inf,3)

X <- matrix(1:6,2,3)
Y <- matrix(2:7,3,2)
X
Y
my.tropical.matrix.prod(X,Y)

library(igraph) 

el <- rbind(c(1,2),c(2,3),c(3,1),c(1,4),c(5,4))
w <- 1:5
g <- graph.edgelist(el) 
plot(g)
# igraphパッケージを使って、いわゆるグラフ距離をグラフアルゴリズムで計算する
D.graph <- distances(g,mode="out",weights=w)

A <- matrix(Inf,5,5) 
for(i in 1:length(w)){
  A[el[i,1],el[i,2]] <- w[i]
}
diag(A) <- 0
A
# グラフ距離計算をトロピカル行列積で計算する関数を作る
my.tropical.shortest.dist <- function(A){
  n <- length(A[,1])
  ret <- A
  for(i in 1:(n-2)){
    ret <- my.tropical.matrix.prod(A,ret)
  }
  return(ret)
}

D.graph.tropical <- my.tropical.shortest.dist(A) 

# 二方法で計算したグラフ距離は一致する
D.graph
D.graph.tropical 
all.equal(D.graph,  D.graph.tropical)

> D.graph
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    3    4  Inf
[2,]    5    0    2    9  Inf
[3,]    3    4    0    7  Inf
[4,]  Inf  Inf  Inf    0  Inf
[5,]  Inf  Inf  Inf    5    0
> D.graph.tropical 
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    3    4  Inf
[2,]    5    0    2    9  Inf
[3,]    3    4    0    7  Inf
[4,]  Inf  Inf  Inf    0  Inf
[5,]  Inf  Inf  Inf    5    0

トロピカル行列式は $\bigoplus_{\sigma \in S([d])} \prod^{\otimes} a_{i,\sigma_i}$ で与えられる
順列の総当たりである値を出し、その最小値を取るので、その最小値がただ一つの順列から得られるか、複数の順列が最小値を返すか、いずれの場合もある。この「重複」に意味があるので、それについても返す関数を作っておく
- ちなみにTropical volumeというものがあって、それは、トロピカル行列式の値が２個（以上）の順列によって与えられるときは０になり、そうでない時には、順列で入れ替えて得られる、最小値と第二最小値の差になる。そのことを $TropVol(A) = |\bigoplus_{\sigma \in S([d])} \prod^{\otimes} a_{i,\sigma_i} - \bigoplus_{\sigma \in S([d]) - \sigma_{opt}} \prod^{\otimes} a_{i,\sigma_i}|$ と表す

トロピカル版の代数学の基本定理

代数学の基本定理は、１変数複素関数には、少なくとも１つ根がある、d次１変数関数ならd個の根がある、というもの(Wiki記事
トロピカル版のそれは、「１変数トロピカル関数」は、(ある条件付き処理を介して) $a \prod_i ^{\otimes} x \oplus r_i)$ と言う形に変形できる。。。この $r_i$ が「根」み見える。と言う話
特に、この $r_i$ は、１変数トロピカル関数の折れ線が曲がるときの $x$ の値に相当しており、トロピカル幾何では、これをトロピカルhypersurface(の１変数版)と呼び、別名、「零点集合」と呼ぶわけだが、この「折線の折れるところ」であって、何も「零」になっていないのに、どうして「零点」なのか、というと、代数学の基本定理的にこの式を見直したときに、「根」に相当する～「零を与えるxの値＝零点」ということらしい
少し、説明を付け加える
$f(x) = \bigoplus_{i = r,r+1,...,n} a_i \otimes x^{i \otimes}$ と表されたとする。r次からn次まで途中を抜かすことなく全部の項を書いた、ということ
これを折線のことを思い出しながら解釈すると、iが大きい項は、急峻な直線を表すが、その直線はトロピカル曲線に参加しやすい。参加しやすいのは $a_i$ の値が大きくても小さくても参加しやすいということ
逆にnが小さい項は $a_i$ の値が大きくなると、トロピカル曲線に参加しない、あってもなくてもよい項になってしまう。そんなとき、「参加しないこと」が真実なのだから、参加させないわけだが、 $a_i$ をどんどん小さくしていくと、いつか、「参加する」ことになって、トロピカル曲線が違うものになってしまう。その事情を考慮して、 $a_i$ の値を変えても良い項については、なるだけ小さな値にまで下げる、というルールを入れることで、トロピカル曲線が与えられたときに、 $a_i$ の値は一意に確定する
さて。このようにして一意化した係数 $a_i$ を用いたトロピカル関数の表記を「Least-coefficient polynomial」と呼ぶ
今、Least-coefficient polynomialが $f(x) = \bigoplus_{i = r,r+1,...,n} a_i \otimes x^{i \otimes}$ であったときに
$f(x) = a_n \prod_{i = n,n-1,...r}^{\otimes} (x \otimes d_i)$ 、但し、 $d_i = a_{i-1} - a_i$ と言う表現があるという
これがトロピカル版の代数学の基本定理
例を。。。
- $f(x) = 3 \otimes x^3 \oplus 1 \otimes x^2 \oplus 2 \otimes x \oplus 4 = min(3+3x,1+2x,x+x,4)$ である
- このとき $a_n = a_3 = 3, a_2-a_3 = 1-3 = -2, a_1 - a_2 = 2 -1 = 1, a_0 -a_1 = 4 - 2 = 2$ なので
- $f(x) = 3 \otimes (x \oplus (-2) \otimes (x \oplus 1) \otimes (x \oplus 2)$ となる、と言う話
こちらのペイパーを：Elementary proof of the fundamental theory of tropical algebra