組合せ最適化セミナー「代数的組合せ最適化」

組合せ最適化セミナー「代数的組合せ最適化」

補足と演習問題

平井広志

東京大学大学院 情報理工学系研究科 数理情報学専攻

[email protected] 平成31年8月6 日

1 Part I

1.1 自由環K⟨x₁, x₂, . . . , x_k⟩

文字x1, x2, . . . , x_kを有限個並べたもの

w=xi1xi2· · ·xim

を語(word)と呼ぶ．空の語を1とかく．２つの語w=x_i1x_i2· · ·x_im, w^′ =x_j1x_j2· · ·x_jm′

の積ww^′は，連結

ww^′ :=x_i1x_i2· · ·x_imx_j1x_j2· · ·x_jm′

で定義される．語のK^{線形結合からなる集合}K⟨x₁, x₂, . . . , x_k⟩と書く．和と積が自然に定 義され，K⟨x1, x2, . . . , xk⟩は（非可換）環となる．1が積の単位元で，0が和の単位元であ る．K⟨x1, x2, . . . , xk⟩^の元は，

5x₁x₂x²₁+ 2x₅x₃x₂x₃

のような形をしている．x1x1 =x²₁と略した．語w =xi1xi2· · ·ximの長さmを次数と呼 んで，degwとかく．K⟨x₁, x₂, . . . , x_k⟩^の元a=∑

wa_wwの次数を dega:= max{degw|aw̸= 0}

で定義する．

補題1(Weak algorithm). 非ゼロなa1, a2, . . . , a_ℓ ∈K⟨x1, x2, . . . , x_k⟩^が，dega1 ≤dega2 ≤

· · · ≤ dega_ℓを満たし，d従属，すなわち，あるb₁, b₂, . . . , b_ℓ ∈ K⟨x₁, x₂, . . . , x_k⟩^が存在 して，

deg(a₁b₁+· · ·+a_ℓb_ℓ)<max

i dega_ib_i

となったとする．このとき，あるj ∈[ℓ]と，c1, c2, . . . , cj−1∈K⟨x1, x2, . . . , xk⟩があって，

deg(a_j −a₁c₁− · · · −a_j−1c_j−1)<dega_j, deg(a_ic_i)≤dega_j (i∈[j−1]).

Proof. d= dega₁b₁=· · ·= dega_ℓb_ℓと仮定してよい．すると degb1≥degb2 ≥ · · · ≥degbℓ

となる．b_ℓのなかで最大次数をもつ項をβw(β∈K\ {0}, w: word)とする．すると βaℓw+

ℓ−1

∑

i=1

ai(bi)^∗ 

は，次数d未満でなければならない．ここで，(bi)^∗は，biから，suffixがwでない項をの ぞいたものである．degbi ≥degb_ℓにも注意する．したがって

a_ℓ+ (1/β)

ℓ−1

∑

i=1

a_i(b_i)^∗/w はdega_ℓ未満で，dega_i(b_i)^∗/w= dega_ℓである．

これは，ある種のユークリッドの互除法を与える．a1, a2, . . . , a_ℓが生成する右イデアル を考える．生成系a₁, a₂, . . . , a_ℓがd従属だと，次数がへるようにある元a_jをとりかえる，

あるいは，除くことができる．これを繰り返すことで，d独立な生成系（基底）にできる．

特に，任意のイデアルは，加群としてみると自由加群になる．このような環を自由イデア ル環（free ideal ring; fir）という．PIDの一般化である．

1.2 Fortin-Reutenauerの定理の証明 易しい方向はスライドで示した．A=∑_k

i=1A_ix_iのinner rankがrとして，K⟨x₁, x₂, . . . , x_k⟩ 上で

A=F G

と分解されたとする．ここで，F ∈K⟨x1, x2, . . . , xk⟩^n×r, G∈K⟨x1, x2, . . . , xk⟩^r×mであ る．我々の目標は，あるK^{上の正則行列}P, Qによって

P AQ= (

B C

O D

)

，

Oは，t×uゼロ行列，n+m−t−u=r，となることを示すことである．

Claim 1. Fの各要素の次数は，1以下としてよい．[非可換性使用]

Proof. 新たな非可換変数y1, y2, . . . , ynを用意する．もしもFに次数が２以上の要素があ るとすると，F Gが次数１なので，行ベクトルy^⊤F の元が補題1の条件を満たすことに なる．K⟨x, y⟩上，正則（可逆）な行列W によって，y^⊤F W をd独立になるようにする と，y^⊤A=y^⊤F W(W⁻¹G) なF W の次数は，1以下，W のy_iに1を代入して，F, Gを F W,(W⁻¹G)におきかえればよい．

Fの次数は1としてよい．もしもゼロならFは，K上の行列で，行変形は，n−r行を ゼロにできる．結果としてAをK^{上の行変形で}(n−r)×mゼロブロックが作れる．

Claim 2. F =F₀+∑

iF_ix_iは，次のように分解できる．[非可換性不使用] U F W =

( F˜ O O I_s

) .

ここで，Uは，K^{上の正則行列，}W は，K⟨x₁, x₂, . . . , x_k⟩上の正則行列（可逆行列），F˜ は次数が1(以下)，つまりF˜= ˜F₀+∑_k

i=1F˜_ix_iで，さらにF˜_i (i= 1,2, . . . , k)の行ベクト ルたちは，K^r−sをスパンする．すなわち







 F˜1

F˜2

... F˜_k









は列フルランク．

Proof. もしも，F_i (i = 1,2, . . . , k)の行ベクトルがK^{r−sをスパンしていれば，}OK．そ うでないとする．K上の列基本変形W0で，FiW0(i= 1,2, . . . , k)の最後の列を(同時に) ゼロベクトルにすることができる．このとき，F0W0の最後の列は，ゼロベクトルであっ てはならない．そうでないとするとF W0の最後の列がゼロベクトルになり，結局Aの

inner rankがrより小さくなる．これは矛盾．したがって，K^{上の行基本変形}U によって，

U F₀W₀の最後の列を，最後の要素を1，それ以外をゼロにすることができる．すると，今 度は，K⟨x₁, x₂, . . . , x_k⟩^{上の列基本変形}W^′によって，F_i (i= 0,1,2, . . . , k)の最後の行を 最後の要素以外をゼロにできる．つまり

U F W0W^′ =

( F˜ 0 0 1

) .

という形にできる．この操作を条件が満たされるまで繰り返す．

さて，U A=U F W W⁻¹Gで，W⁻¹G= (

G1

G₂ )

とすると

U A=

( F˜ O O Is

)

W⁻¹G=

( F G˜ ₁ G2

) . G₁は，(r−s)×r行列である．

Claim 3. G₁の各要素の次数はゼロ，つまり，G₁は，K^{上の行列．} [非可換性使用] Proof. G1の次数d >1の斉次成分を∑

wHwwとかく．ここで，wは長さdのwordを動く．

Hwは，K^{上の行列である．}U Aは1次なので，∑

wF H˜ ww= 0，特に∑

w

∑_k

i=1F˜iHwxiw= 0．word x_iw (i= 1,2, . . . , k)はすべて異なるので，任意のwに対して，F˜_iH_w = 0 (i= 1,2, . . . , k)．F˜_i (i= 1,2, . . . , k)の行ベクトルは，K^{r−sをスパンするので，}H_w = 0．した がって，G₁の次数d >1の斉次成分はゼロとなる．

W⁻¹GにK^{上の列基本変形}V によって，G₁ を対角行列になるようにする．すると，

inner-rankがrであることから

W⁻¹GV = (

I_r−s O

C D

)

とすることができる．すると

U AV = (U F W)(W⁻¹GV) =

( F˜ O O Is

) (

Ir−s O

C D

)

=

( F˜ O

C D

)

最後のゼロブロックのサイズは，(n−s)×(m−r+s)なので，u=n−s,t=m−r+s とすると，m+n−u−t=rとなる．

定理 2 (Fortin-Reutenauer 2004). nc-rankA≤2 rankA.

Proof. A = ∑_k

i=1Aixiとして，Ai たちがK上スパンする行列空間をAとする．このと き，rankA ≥ maxA˜∈Arank ˜Aに注意する．なお，Kのサイズが大きいときは等号成立．

r= maxA˜∈Arank ˜Aを達成する（K^{上の）行列}A˜をとる．K^{上の正則行列}P, Qにより PAQ˜ =

( I_r O

O O

)

とできる．任意のB˜ ∈ A^{に対して，}

PBQ˜ = (

C D

E O

)

の形になることをしめす．ここでCはr×r行列．するとnc-rankA ≤ 2r ≤ 2 rankAと なる．

A˜はA^{でランク最大なので，}At˜ + ˜Bのランクは，r以下．したがって，At˜ + ˜B ∈ A^の ランクもr以下．P( ˜At+ ˜B)Qの最初のr行r列を含むr+ 1次部分行列式

det (

C^′+tI ∗

∗ b˜^′ )

を考えると，t^rの係数は，b˜^′ := (PBQ)˜ ij (i, j > r)である．Kのサイズが大きい場合はこ れが多項式としてゼロでなくてはいけないので，(PBQ)˜ ij = 0となる．K^{のサイズが小さ} い場合はよくわからなかった．

1.3 行列のクロネッカー積

行列B= (b_ij), C = (c_ij)のクロネッカー積B⊗Cは

B⊗C:=





b11C b12C · · · b₂₁C b₂₂C · · · ... ... . ..





と定義される．Bがn×m，Cがn^′×m^′のときは，B⊗Cはnn^′×mm^′である．C⊗B はC⊗Bを並べ替えると得られることに注意する．

• BB^′,CC^′が定義できるなら

(B⊗C)(B^′⊗C^′) = (B^′B⊗CC^′).

(ヒント．ブロック行列の掛け算をつかう)

• trB⊗C= trBtrC.

• detB⊗I = detI⊗B= detB^d．ここで，Iはd×d単位行列．

補題 3 (Hrubeˇs, Wigderson 2015).

A=∑

iAixiが，nc-正則⇔ ^あるDi ∈K^{d×dによって，}det∑

iAi⊗Di̸= 0.

Proof. (⇒) あるB ∈ K(⟨x1, x2, . . . , xn⟩)^n×nがあって，BA = AB = I．これは，ある Di ∈K^{d×dによって，}B(D1, D2, . . . , Dn)が定義できて，B(D1, D2, . . . , Dn)(∑

iAi⊗Di) = (∑

iAi⊗Di)B(D1, D2, . . . , Dn) =Iを意味する．つまり，B(D1, D2, . . . , Dn)は∑

iAi⊗Di

の逆行列で，det∑

iA_i⊗D_i̸= 0.

(⇐) A = ∑

iA_ix_iが，nc-非正則なら，Fortin-Reutenauerの定理より，K^{上正則行列} P, Qにより

P AQ= (

C D

O E

)

とできる．ここで，Oはr×sゼロ行列でr+s > nである．すると任意のD_i ∈K^d×dに 対して，

(P ⊗I)(∑

i

Ai⊗Di)(Q⊗I) = (∑

i

P AiQ)⊗Di= (

C^′ D^′ O^′ E^′

)

となる．ここで，O^′はrd×sdゼロ行列で，rd+sd > ndである．すなわち，∑

iAi⊗Di

は可逆でない．つまり，det∑

iAi⊗Di= 0.

2 Part II

2.1 行列スケーリングの収束性の補足

補題 4. B1=1,∥B^⊤1−1∥² <1/nなら，G_Bには完全マッチングが存在する．

Proof. 対偶を示す．G_Bには完全マッチングが存在しないと仮定する．すると，Hallの定

理からBは，行と列を並べ替えることで B =

(

C D

O E

)

となる．ここで，Oは，r×sゼロ行列でr+s > nである．(c₁ c₂ . . . c_n) :=1^⊤Bを列 和ベクトルとする．B1=1から，Eの要素の総和はrである．これより，

∑n i=s+1

ci ≥r を得る．

∥B^⊤1−1∥² =

∑n i=1

(c_i−1)²≥

∑n i=s+1

(c_i−1)²

≥ 1

n−s(

∑n i=s+1

(ci−1))² = 1 n−s(

∑n i=s+1

ci−n+s)²

≥ 1

n−s(r−n+s)² > 1 n−s > 1

n.

ここで，２つ目の不等式では，２次関数の凸性，３つ目の不等式では，r +s > n と

∑_n

i=s+1c_i ≥rを用いた．

補題 5. B1=1，または，B^⊤1=1なら，Cap(B)≤1.

Proof. Cap(B) ≤ ∏

i(A1)i ≤ (1^⊤B1/n)ⁿ = 1. ここで，不等号は相加相乗平均を用い た．

補題 6. B1=1で，∥B^⊤1−1∥² =ϵなら，Cap(C(B))≥(1 + Ω(ϵ))Cap(B). RとCの 役割を換えても成立．

Proof. (c₁ c₂ . . . c_n) :=1^⊤Bを列和ベクトルとする．すると Cap(C(B)) = (c1c2· · ·cn)⁻¹Cap(B).

ここで

c1c2· · ·cn= (1 + (c1−1))(1 + (c2−1))· · ·(1 + (cn−1))

∼exp(∑

i

(ci−1)−1 2

∑

i

(ci−1)²)

= exp(−ϵ/2).

最後の等号で∑

ici =nと∑

i(ci−1)² =ϵを用いた．

2.2 作用素スケーリングの収束性の補足

補題 7. TA(I) =I，または，T_A^∗(I) =Iなら，Cap(TA)≤1.

Proof. X=IにたいしてCap(T_A)≤det∑

iA_iA^†_i ≤n(tr∑

iA_iA^†_i)^1/n=n(tr∑

iA^†_iA_i)^1/n からわかる．不等式は，固有値に関する相加相乗平均，最後の等式は，トレースの線形性 を用いる．

補題 8. T_A^∗(I) =Iで，∥T_A(I)−I∥² =ϵなら，Cap(R(T_A))≥(1 + Ω(ϵ))Cap(T_A). Rと Cの役割を換えても成立．

Proof. まず，

Cap(C(T_A)) = (det(T_A))⁻¹Cap(T_A).

に注意する．c1, c2,· · ·, cnをT_Aの固有値とすると，∥T_A(I)−I∥²=ϵより，∑

i(ci−1)² =ϵ で，T_A^∗(I) =Iより，∑

ic_i= trT_A(I) = trT_A^∗(I) = trI =n．よって，

detTA = c1c2· · ·cn= (1 + (c1−1))(1 + (c2−1))· · ·(1 + (cn−1))

∼exp(∑

i

(c_i−1)−1 2

∑

i

(c_i−1)²)

= exp(−ϵ/2).

最後の等号で∑

ici =nと∑

i(ci−1)² =ϵを用いた．

3 Part III

3.1 モジュラ束

半順序集合P^の２元a, bのジョインとは，a, bの最小の共通上界のことで，（それが存在 するならば）a∨bであらわす．最大の共通下界をミートといってa∧bであらわす．任意 の２元に対してジョインとミートが存在するとき，P^{を束という．}P ^{の高さ関数（}height function）とは，r :P →Z^{であって，}

r(b) =r(a) + 1 (a≺b:̸ ∃c:a≺c≺b)

を満たすものである．高さ関数が存在するとき，Pは階層的であるという．

束（lattice）L^{がモジュラ束（}modular lattice）であるとは，任意のa, b, c∈ L:a⪰c に対し，a∧(b∨c) = (a∧b)∨cが満たされるときをいう．ここでは高さ関数rをもつ束 のみについて考えるものとする．以下はよく知られている．

補題 9. 高さ関数rをもつ束Lに対して，以下は同値：

• L^{はモジュラ束．}

• r:L →Z^は，

r(x) +r(y) =r(x∧y) +r(x∨y) (x, y∈ L) を満たす．

補題10. Uを体K上の有限次元ベクトルとする．S(U)をUの部分ベクトル空間全体から なる半順序集合とする．順序は包含関係とする．このとき，S(U)はモジュラ束で，∧=∩,

∨= +, r= dimとなる．

Proof. 部分空間は∩^と+で閉じているから，∧=∩, ∨= +であり，r = dimも明らか．

X, Y, Z ∈ S(U) :X ⊇Zに対し，明らかにX∩(Y +Z)⊇(X∩Y) +Zが成り立つ．逆を 包含がいえればよい．u=y+z∈X∩(Y +Z) :y ∈Y, z ∈Zに対して，y =u−z∈X (z∈Z ⊆X∋uより）なので，u=y+z∈(X∩Y) +Zである．

3.2 オーソスキーム複体

オーソスキーム複体(orthoscheme complex)のフォーマルな定義を述べる．P ^を高さ 関数をもつ階層的な半順序集合とする．オーソスキーム複体K(P)はP ^{のチェインの形} 式的凸結合の全体からなる．すなわち，K(P)はx = ∑_m

k=0λkpk, p0 ≺ p1 ≺ · · · ≺ pm,

∑_m

k=0λk= 1，λk≥0 (∀k)となる元xたちからなる．一つのチェインの凸結合全体を単体 と呼ぶことにする．K(P)の距離構造は以下のように導入される．極大な単体C(長さn) からRⁿへの写像φ_C を

φ_C(x) :=

∑n k=1

λ_k(e1+· · ·+e_k) (x=

∑n k=0

λ_kp_k).

と定める．ここで単体Cは，極大チェインp0≺p1 ≺ · · · ≺pnの凸結合とし，eiはRⁿの 単位ベクトルである．そして，C内の2点x, yの距離d(x, y)を∥φ_C(x)−φ_C(y)∥2で定め る．次に，K(P)内のパスγ : [0,1]→K(P)の長さd(γ)を

d(γ) := sup

k−1

∑

i=0

d(γ(t_i), γ(t_i+1))

と定義する．ここでsupはγ(t_i), γ(t_i+1)が同じ単体に属するような十分細かい区間分割 0 =t₀ < t₁ < · · ·< t_k = 1 (k > 0)についてとる．そして，K(P)の2点の距離をその ２点を結ぶパスの長さの下限として定義する．P が階層的であることから，この定義は

well-definedで，K(P)は距離空間となり，P のオーソスキーム複体と呼ぶ．直感的にい

うと，各極大チェインに対して頂点0, e1, e1+e2, . . . , e1+e2+· · ·+enを持つRⁿの単体 を詰めて得られる空間がK(P)である．P ^{の順序複体（}order complex）の幾何学的実現 に特殊な距離を入れたものともいえる．

4

1. (線形マトロイド交差) 行列A = (a1 a2 · · · a_k) に対して線形マトロイドM(A) = (E,I(A))を

I(A) :={I ⊆[k]|a_i (i∈I)は一次独立}

と定義される．もう一つの行列B = (b₁ b₂ · · · b_k) とそのマトロイドM(B) = ([k],I(B))を考える.

(i) 以下の等式を示せ．

max{|I| |I ∈ I(A)∩ I(B)}= rank

∑k i=1

a_ib^⊤_i x_i

ヒント. Binet-Cauchyの公式を用いてもよい．Binet-Cauchyの公式について は，ググってください．

(ii) A=∑_k

i=1aib^⊤_i xiとおくとき，

rankA= nc-rankA

を示せ．ヒント. Edmondsのマトロイド交差定理（ググってください）を用い てよい．

(iii) 共通独立集合I ∈ I(A)∩ I(B)に対して，A˜=∑

i∈Ia_ib^⊤_i z_i (z_i∈K)とすると き，A˜のWong sequenceを計算せよ．

2. (i) 非２部グラフの最大マッチングをEdmonds問題として定式化せよ．ヒント．

Tutte行列

(ii) (線形マトロイドマッチング) 行列A= (a₁ b₁ a₂ b₂ · · · a_k b_k)に対して独立集 合J(A)⊆2^[k]を

J(A) :={J ⊆[k]|ai, bi (i∈J)が一次独立} と定義する．このとき

2 max{|J| |J ∈ J(A)}= rank∑

i

(a_ib^⊤_i −b_ia^⊤_i )x_i を示せ．

(iii) rankA <nc-rankAとなるA=∑

iA_ix_iを与えよ．

3. (i) G_Bに完全マッチングが存在しなければ，Cap(B) = 0となることを示せ．

(ii) A=∑

iAixiがnc-非正則なら，Cap(TA) = 0となることを示せ．

4. Cap(B)の最適化問題は，変数変換をすることで，凸計画になることをしめせ．

5. (i) Cap^sym(B) =n(Cap(B))^1/nを示せ．

(ii) Cap^sym(T_A) =n(Cap(T_A))^1/nを示せ．そして，作用素スケーリングがCap^sym(T_A) に対する交互最適化とみなせることを示せ．  

ヒント：ラグランジュの未定乗数法 6. tr(∑

iD_i⊗C_i)(∑

iD_i⊗C_i)^†≤tr∑

iD_iD_i^†tr∑

iC_iC_i^†.を示せ．ヒント．trC⊗D= trCtrDに注意する．

7. Aがブロック行列A_ij (i∈[n], j∈[m])によって

A=









A11x11 A12x12 · · · A1mx1m

A21x21 A22x22 · · · A2mx2m

... ... . .. ... An1xn1 An2xn2 · · · Anmxnm









の形をしているとき，MVSPの最適解(X, Y)として，

X = X1⊕X2⊕ · · · ⊕Xn, Y = Y₁⊕Y₂⊕ · · · ⊕Y_m, Aij(Xi, Yj) = {0} (i∈[n], j∈[m]) となるものがとれることを示せ．

8. Mを行列とし，双線形形式とみる．(X, Y) 7→ rankM|X×Y が劣モジュラ関数であ ること，つまり，

rankM|X×Y + rankM|X^′×Y^′ ≥rankM|(X∩X^′)×(Y+Y^′)+ rankM|(X+X^′)×(Y∩Y^′)

を示せ．ヒント: X, X^′, X∩X^′, X+X^′,Y, Y^′, Y ∩Y^′, Y +Y^′をgenerateする基底 をとって考える．

9. L^{をベクトル空間}Kⁿの部分空間からなるモジュラ束とする．L^{の２つの極大チェイ} ンC:{0}=X₀ ⊂X₁ ⊂ · · · ⊂X_n=K^n，D:{0}=Y₀ ⊂Y₁⊂ · · · ⊂Y_n=K^nに対 して，K^nの基底a₁, a₂, . . . , a_nが存在して，C, Dは，a₁, a₂, . . . , a_n達からgenerate される部分束（ブール束2^[n]に同型）に含まれることを示せ．

ヒント：例えば，次元nに関する帰納法，X_n−1内の２つの極大チェインC^′ :X₀ ⊂ X₁ ⊂ · · · ⊂X_n−1とD^′ =D∩X_n−1を考えて．．．

10. 2つのn×k行列A= (a₁ a₂ · · · a_k), B = (b₁ b₂ · · · b_k)と整数c₁, c₂, . . . , c_k ∈Z に対して，行列

A:=

∑k i=1

t^ciaib^⊤_i xi

を考える．x₁, x₂, . . . , x_k, tは変数である．

(i) このとき

deg detA= max{c(I)|I ⊆ I(A)∩ I(B) :|I|=n} を示せ．

(ii) deg DetA= deg detAを示せ．ヒント：問題1の結果を利用する．

参考文献

[1] Z. Allen-Zhu, A. Garg, Y. Li, R. Oliveira, A. Wigderson, Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Test- ing, Proceedings of the Symposium on Theory of Computing (STOC’18)(2018), pp.

172-181.

[2] S. A. Amitsur: Rational identities and applications to algebra and geometry,Journal of Algebra 3 (1966) 304–359.

[3] M. Baˇc´ak, Convex Analysis and Optimization in Hadamard Spaces. De Gruyter, Berlin, 2014.

[4] M. Baˇc´ak: Old and new challenges in Hadamard spaces, preprint, 2018, arXiv:1807.01355.

[5] T. Brady and J. McCammond, Braids, posets and orthoschemes. Algebraic and Ge- ometric Topology 10(2010), 2277–2314.

[6] P. Burgisser, C. Franks, A. Garg, R. Oliveira, M. Walter, A. Wigderson, Efficient algorithms for tensor scaling, quantum marginals and moment polytopes,Proceedings of Foundations of Computer Science (FOCS’18) 2018.

[7] M. R. Bridson and A. Haefliger,Metric Spaces of Non-positive Curvature. Springer- Verlag, Berlin, 1999.

[8] J. Chalopin, V. Chepoi, H. Hirai, and D. Osajda. Weakly modular graphs and non- positive curvature. Memoirs of the AMS, to appear.

[9] P. M. Cohn: Free Rings and Their Relations, Second Edition Academic Press, Lon- don, 1989.

[10] P. M. Cohn: Algebra. Vol. 3. Second Edition,John Wiley & Sons, Chichester, 1991.

[11] P. M. Cohn: Skew Fields. Theory of General Division Rings,Cambridge University Press, Cambridge, 1995.

[12] H. Derksen and V. Makam, Polynomial degree bounds for matrix semi-invariants.

Advances in Mathematics 310 (2017), 44–63.

[13] J. Dieudonn´e: Les d´eterminants sur un corps non commutatif,Bulletin de la Soci´et´e Math´ematique de France 71(1943). 27–45.

[14] J. Edmonds, Systems of distinct representatives and linear algebra.Journal of Re- search of the National Bureau of Standards 71B (1967) 241–245.

[15] M. Fortin and C. Reutenauer, Commutative/non-commuative rank of linear matri- ces and subspaces of matrices of low rank. S´eminaire Lotharingien de Combinatoire 52(2004), B52f.

[16] S. Fujishige, T Kir´aly, K. Makino, K. Takazawa, and S. Tanigawa: Minimizing Submodular Functions on Diamonds via Generalized Fractional Matroid Matchings, EGRES Technical Report (TR-2014-14), (2014).

[17] A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson: Operator scaling: theory and applications. Foundations of Computational Mathematics(2019).

[18] A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson: Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling. Geometric and Func- tional Analysis 28(2018), 100–145.

[19] K. R. Goodearl and R. B. Warfield, Jr.: An Introduction to Noncommutative Noetherian Rings. Second Edition,Cambridge University Press, Cambridge, 2004.

[20] L. Gurvits, Classical complexity and quantum entanglement.Journal of Computer and System Sciences 69(2004), 448–484.

[21] M. Hamada and H. Hirai: Maximum vanishing subspace problem, CAT(0)- space relaxation, and block-triangularization of partitioned matrix, 2017, arXiv:1705.02060.

[22] H. Hirai: Discrete Convex Functions on Graphs and Their Algorithmic Applica- tions, In: T. Fukunaga and K. Kawarabayashi (eds.) Combinatorial Optimization and Graph Algorithms, Communications of NII Shonan Meetings, Springer Nature, Singapore, (2017), pp. 67–101.

[23] H. Hirai: Uniform modular lattice and Euclidean building, preprint, 2017, arXiv:1801.0024.

[24] H. Hirai, Computing DM-decomposition of a partitioned matrix with rank-1 blocks.

Linear Algebra and Its Applications 547(2018), 105–123.

[25] H. Hirai, L-convexity on graph structures.Journal of the Operations Research So- ciety of Japan61 (2018), 71–109.

[26] H. Hirai, Computing the degree of determinants via discrete convex optimization on Euclidean buildings,SIAM Journal on Applied Geometry and Algebra, to appear.

[27] P. Hrubeˇs and A. Wigderson, Non-commutative arithmetic circuits with division, Theory of Computing 11(2015), 357–393.

[28] G. Ivanyos, M. Karpinski, and Y. Qiao, and M. Santha: Generalized Wong se- quences and their applications to Edmonds’ problems, Journal of Computer and System Sciences 81(2015), 1373–1386.

[29] G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Non-commutative Edmonds’ prob- lem and matrix semi-invariants.Computational Complexity 26(2017) 717–763.

[30] G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristics.

Computational Complexity 27(2018), 561–593.

[31] H. Ito, S. Iwata, and K. Murota, Block-triangularizations of partitioned matrices under similarity/equivalence transformations.SIAM Journal on Matrix Analysis and Applications 15(1994), 1226–1255.

[32] S. Iwata and K. Murota, A minimax theorem and a Dulmage-Mendelsohn type decomposition for a class of generic partitioned matrices. SIAM Journal on Matrix Analysis and Applications 16(1995), 719–734.

[33] N. Linial, A. Samorodnitsky, and A. Wigderson, A deterministic strongly polyno- mial algorithm for matrix scaling and approximate permanents, Combinatorica 20 (2000), 545–568.

[34] L. Lov´asz, Submodular functions and convexity. In A. Bachem, M. Gr¨otschel, and B. Korte (eds.): Mathematical Programming—The State of the Art(Springer-Verlag, Berlin, 1983), 235–257.

[35] L. Lov´asz, Singular spaces of matrices and their application in combinatorics.Bo- letim da Sociedade Brasileira de Matem´atica 20(1989), 87–99.

[36] L. Lov´asz and M. Plummer, Matching Theory, North-Holland, Amsterdam, 1986.

[37] K. Murota, Matrices and Matroids for Systems Analysis. Springer-Verlag, Berlin, 2000.

[38] T. Oki, Computing the Maximum Degree of Minors in Skew Polynomial Matrices, preprint, (2019),arXiv:1907.04512.

[39] S. Ohta and M. P´alfia. Discrete-time gradient flows and law of large numbers in Alexandrov spaces. Calculus of Variations and Partial Differential Equations 54 (2015) 1591–1610.

[40] O. E. Raz, and A. Wigderson, Subspace arrangements, graph rigidity and deran- domization, (2019), arXiv:1901.09423.

[41] L. Taelman: Dieudonn´e determinants for skew polynomial rings,Journal of Algebra and Its Applications 5(2006) 89–93.