線形代数

3 Adjacency Matrix ぱらぱらめくる『Graphs and Matrices』

隣接行列Aのm乗の(i,j)要素の値は、i,j間のグラフ距離 3.1 Eigenvalues n完全グラフの隣接行列の固有値は、1がn-1重で-1が1個。p,q-完全2部グラフのそれはとp+q-2重の0 Full-cycle permutation matrix of order nの場合、隣接行列の固有値は、 n頂点を結ぶパ…

10 Laplacian Eigenvalues of Threshold Graphs ぱらぱらめくる『Graphs and Matrices』

10.1 Majorization ベクトルの要素の和が等しいような2つのベクトルがあって、その累積和ベクトルの要素のすべてについて、後者のそれが前者のそれ以上であるとき、前者は後者でMajorzationされているという そのMajorizationでできる行列がある 10.2 Thres…

9 Resistance Distance ぱらぱらめくる『Graphs and Matrices』

Distance を考えるとき、最短経路のみが問題になるが、非最短経路との相対的な関係で最短経路とその距離とを考えることも有用。そのような距離がResistance distance Laplacianの章で出てきた行列H(g-inverse of L)を使うと となる 三角不等式も成り立つ ネ…

ぱらぱらめくる『Graphs and Matrices』2 Incidence Matrix

2.1 ランク 有向グラフGのn個のノードと、m個のエッジ。nxm行列で、エッジの始点と終点とを1,-1で表したもの、それがIncidence matrix Q(G) Q(G)の列和はゼロ、行ベクトルは線形非独立 連結グラフのランクはn-1、k個の連結グラフの集合ならランクはn-k k個の…

8 Distance Matrix of a Tree ぱらぱらめくる『Graphs and Matrices』

木のDistance matrixの場合、 木でないグラフのDistance matrixの場合は、サイクルとそうでない部分(木)に分けて行く 木のDistance matrixのLaplacian、固有値を考えることで有用な性質がある

7 Algebraic Connectivity ぱらぱらめくる『Graphs and Matrices』

Laplacian matrixの最小固有値は0。二番目に小さい固有値をalgebraic connectivityと言う。非連結グラフのalgebraic connectivityは0。完全グラフのそれはn 7.1 Preliminary results 7.2 Classification of trees(Types I and II) 7.3 Monotocinicty propert…

ぱらぱらめくる『Graphs and Matrices』大雑把なまとめ

グラフはノードとエッジでできており、それにIDを振ると色々な行列が出来る 行列は正方行列と非正方行列とがある 非正方行列の代表はIncidence matrix(ノードとエッジの関係を表した行列) 正方行列はノードxノードの行列があり、いろいろある グラフの特徴…

6 Regular Graphs ぱらぱらめくる『Graphs and Matrices』

全ノードの次数が等しいグラフがRegular 6.1 Perron-Frobenius theory 成分が正である実正方行列には唯一つの最大実固有値が存在し、それに対応する固有ベクトルの各成分は厳密に正である、という主張。グラフのノードの重みづけ(ページランク)計算などに用…

5 Cycles and Cuts ぱらぱらめくる『Graphs and Matrices』

Incidence matrix Qのnull spaceをcycle subspace、Q^Tのnull space を cut subspaceと呼ぶ edgeのセットをうまく取り出して足し合わせると、キャンセルアウトするのがcycleなので、incidence matrixのcolumnsの線形和でゼロベクトルができれば、その線形和…

ぱらぱらめくる『Graphs and Matrices』1 Preliminaries

1.1 Matrices 行列、転置、対角行列 Trace and determinent ベクトル空間とランク Minorsは行の一部と列の一部とを取り出した部分行列。と書くと、行の部分集合S、列の部分集合TでのMinor。はSとTの補集合によるMinor。は1行、1列を除いたMinor 特に、行と…

4 Laplacian Matrix ぱらぱらめくる『Graphs and Matrices』

エッジが無いノードペアは0、エッジありのペアは-1、対角成分はノードの次数であるような行列がLaplacian matrix L=D-A (ただし、Dは対角行列で対角成分がノードの次数、Aはadjacency matrix) L=Q Q^T (ただしQはincidence matrix)でもある Lは対称で半正定…

ぱらぱらめくる『Graphs and Matrices』

Graphs and Matrices (Universitext)作者: Ravindra B. Bapat出版社/メーカー: Springer発売日: 2014/10/02メディア: ペーパーバックこの商品を含むブログを見る 目次 1 Preliminaries 2 Incidence Matrix 3 Adjacency Matrix 4 Laplacian Matrix 5 Cycles a…

ジョルダン標準形

正方行列は一次独立な線形変換することで、単純な形にすることができる ここで言う単純な形とは、対角成分付近にのみ値があって、それ以外の成分が0であるような行列のことである 実際、線形変換によって、対角成分勝ちにしたときに、その対角成分勝ちな成分…

ちょっとずらして解く

(Mは正方行列、xはベクトル)を解くと、Mのdeterminantが0出なければ、xは0ベクトルになるけれど、それが欲しいわけじゃなくて、をだいたい満足するxが欲しいときの話 こちらにあるようにWillmoreフローの計算機解の一環として、次のような問題がある を解き…

CHOLMODとか

CHOLMODなどのヘッダーファイル、コードファイルの検索ができるAmesos packageのDoxgenサイト ぽんのブログさんの記事 そもそもコレスキー分解経由でのAx=bの解法とはどうなっているか→こちら

線形代数〜数値解析諸法に慣れる〜scipy

# 適当に正方行列を作る n = 100 m = np.array(np.random.randn(n**2)).reshape(n,n) # Determinant linalg.det(m) # 逆行列 m_inv = linalg.inv(m) np.allclose(np.dot(m, m_inv), np.eye(n)) # 特異値分解 u, s, v = linalg.svd(m) s_ = np.diag(s) # 特異…

幾何代数

「代数幾何(algebraic geometry)」と「幾何代数(geometrix algebra)」は違う Geometric algebraはgeometric productを使う。Geometric productは「スカラーとベクトルの和()」を返す 線形代数はユークリッド幾何に使いやすい 非ユークリッド幾何(の中でも特…

ぱらぱらめくる『Geometric Algebra in Linear Algebra and Geometry』

種本→こちら 目次 1. イントロ 2. 幾何代数と行列(linear and multi-linear algebra on n-dimensional real vector space: "null space", 2^n基底のGrassmann algebra) 3. 幾何代数と非ユークリッド幾何(affine, projectiev and other non-euclidean geometr…

数学セミナーの連載「線形代数と数え上げ」

第1回 平面分割と非交差経路 第2回 LGV公式 第3回 平面分割とシューア函数 第4回 ヤコビ-トゥルーディ公式 第5回 非交差経路とフェルミオン 第6回 ワイルの指標公式 第7回 マクマホンの公式 第8回 平面分割の対角断面 第9回 平面分割と非交差閉路 …

パーマネントの計算

こちらは概論 パーマネントについて(Wiki) 論文(こちら)はインポータンスサンプリング こちらもインポータンスサンプリング こちらも?(コード付き) こちら性能評価とか? こちらは関係ないかもしれないけれども こちらも こちらも こちらは? こちら こちら…

ただのメモ

次元空間に次のような線形な次元亜空間Sがある Sは、あるS上の点を通り、個の線形独立なベクトルによって張られている 上にあって、の外の点をとし、そのSへの垂線の足をとする ここでとする 今、はS上の点であるから、、ただしと表せる また、ABはSに垂直で…

状態変化とルール

囲碁は19x19の格子座標の値が0(何もない)、1(黒石)、-1(白石)の3状態をとることで表現できる(こちら) 石が囲まれて取られる、というルールは、ある連続領域(ムーア近傍は連続しているとみなす)が1で、その領域のムーア近傍が-1となったときに1の石はすべて座…

周期データのパラメタ推定

こちらの続き 複素関数を用いた周期データの変数表現があった 複素数は2つの実数からなる(実部と虚部) 複数の実数に関する回帰・最適化問題は、いろいろなやり方がある 掲載図はoptim()関数を使ってみた例 緑が理論値、黒が実測値(理論値からのずれを正規分…

周期データの多次元角座標パラメタ処理

k次元 固有値の数がk個 すべての固有値はノルムが1の複素数だから、k個の角パラメタを用いて と表せる ノルムが1の複素数k次元ベクトルがk個 ノルムが1の第j番目の複素数k次元ベクトルは、を満足する実変数と、k個の角変数を用いて 上の記事のように、をk…

周期データのパラメタ化

こちらの続き k次元の複素数ベクトルのノルムを1にするために、なるを作りたい データをうまく説明するように変数を回帰推定するためには、うまく取り扱いたい 多次元極座標を用いて行うことにすれば、以下のように。。。 k<-3 # 次元 v<-runif(k) sphereCo…

複素数を使って周回させる

状態数がk個あり、それらは量を持ち、時間とともに変化するとする 次時刻の状態の量は、現時刻の量から線形に決まるとする 状態推移はkxk行列 M で表される 今、ある状態から始まって、Mがt回適用されたときに、元の状態に戻ることを、周期的とする 周期的な…

Gating

Gatingは膜電位・神経生理の世界で用いられる言葉(Wikipedia) 0/1の情報に量子化する作用とも言える こちらで時系列パターンの発生を見ている たった一つの推移行列があって、それが離散的なとき(要素が0,1のみでできている推移行列の場合)には、複数の循環…

複雑な周期性をシミュレーションする

こちらやこちらで時系列解析について少しまとめた。周期性に関する解析だった 漸化式的な変化の線形代数処理についてはこちらで触れた。時間進行に伴って、確定的だった 順列と置換に関して線形代数的にこちらに書いた。要素を部分集合に分割し、部分集合内…

BLAS (Basic Linear Algebra Subprograms)

BLASは線形代数の計算仕様書のようなもの 以下の演算のうち、「こういう演算」は基本関数として作りましょう、という仕様書です(本家のサイト)。少し噛み砕いた説明サイト。 実際には、その仕様書にしたがって、「こういう風に(適切に)実装した」という実装…