注目の投稿

技術Note一覧

このブログのメインコンテンツである技術Noteの一覧

2016/11/15

ユニモジュラ行列

LAMBDA法でも出て来るユニモジュラ行列.

幾何学的に解釈すると面白い性質を持っていそうだ.


暗号理論のための格子の数学(D.ミッチアンチオ )より
・基底ベクトルの整数倍の線形結合で表される整数格子点の集合を変化させない行列.
・ユニモジュラ行列による変換は基底ベクトル列からなる行列の行列式を変化させない=基底ベクトルの張る平行四辺形の等積変形に等価
参考
https://grampus.jaist.ac.jp/hiss/lattice/091109-revise.pdf


http://www.misojiro.t.u-tokyo.ac.jp/~murota/lect-surikeikakuhou/integerprogunimod101222.pdf

http://dopal.cs.uec.ac.jp/okamotoy/lect/2014/fdopt/handout07.pdf より
・整凸多面体の頂点という概念が面白そう.
・整数計画問題,離散最適化でも使われている
・グラフ理論でも使われている


電気通信大学 岡本先生の離散最適化の講義資料が分かりやすそう.特に2014年度にLAMBDA法につながる整数最適化の重要概念が濃縮されている感.
http://dopal.cs.uec.ac.jp/okamotoy/lect/2016/treewidth/#past