2017-10-28

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

1.1 Matrices
- 行列、転置、対角行列
- Trace and determinent
  - $traceA = \sum a_{ii}$
  - $detA = \sum_{\sigma} sgn(\sigma) \prod a_{i \sigma(i)}$
- ベクトル空間とランク
- Minorsは行の一部と列の一部とを取り出した部分行列。と書くと、行の部分集合S、列の部分集合TでのMinor。はSとTの補集合によるMinor。は１行、１列を除いたMinor
  - 特に、行と列とのそれぞれの部分集合が対応したものであるとき、それはPrincipal submatrix
- Nonsingular matrices
  - 逆行列がある
  - ランクがn
  - adjointを使うと $A^{-1} = \frac{1}{detA} (a_{ij})$ 、ただし $a_{ij} = (-1)^{i+j} detA(i|j)$
  - Full column rank とfull row rank。full column rankを持てば $XB=I$ なる左から掛けて単位行列にする行列Xがあり、full row rankを持てば $CY=I$ のように右から掛けて単位行列にする行列Yがある。行列は $A=BC$ (Bはfull column rank、Cはfull row rank)と表せる。また $A=PI'Q$ (ただし、I'は、1...r (rはAのランク)の対角成分が1で、それ以外は0である行列で、P、Qはそれぞれnonsingular)と分解できる。これがrank factorization
- Orthogonal。直交、内積がゼロ。その集まり直交基底。Gram-Schmidt orthogonalizationで、線形独立な行列から正規直交基底が作れる(QR分解より融通が利く…)

library(far)
mat1 <- matrix(c(1,0,1,1,1,0),nrow=3,ncol=2)
mat1
orth1 <- orthonormalization(mat1, basis=FALSE, norm=FALSE)
orth1
orth2 <- orthonormalization(mat1, basis=FALSE, norm=TRUE)
orth2
orth3 <- orthonormalization(mat1, basis=TRUE, norm=TRUE)
orth3
Q <- qr.Q(qr(mat1))
crossprod(orth1)
crossprod(orth2)
crossprod(orth3)
crossprod(Q)

> mat1 <- matrix(c(1,0,1,1,1,0),nrow=3,ncol=2)
> mat1
     [,1] [,2]
[1,]    1    1
[2,]    0    1
[3,]    1    0
> orth1 <- orthonormalization(mat1, basis=FALSE, norm=FALSE)
> orth1
     [,1] [,2]
[1,]    1  0.5
[2,]    0  1.0
[3,]    1 -0.5
> orth2 <- orthonormalization(mat1, basis=FALSE, norm=TRUE)
> orth2
          [,1]       [,2]
[1,] 0.7071068  0.4082483
[2,] 0.0000000  0.8164966
[3,] 0.7071068 -0.4082483
> orth3 <- orthonormalization(mat1, basis=TRUE, norm=TRUE)
> orth3
          [,1]       [,2]       [,3]
[1,] 0.7071068  0.4082483 -0.5773503
[2,] 0.0000000  0.8164966  0.5773503
[3,] 0.7071068 -0.4082483  0.5773503
> Q <- qr.Q(qr(mat1))
> crossprod(orth1)
     [,1] [,2]
[1,]    2  0.0
[2,]    0  1.5
> crossprod(orth2)
     [,1] [,2]
[1,]    1    0
[2,]    0    1
> crossprod(orth3)
     [,1]          [,2]          [,3]
[1,]    1  0.000000e+00  0.000000e+00
[2,]    0  1.000000e+00 -1.110223e-16
[3,]    0 -1.110223e-16  1.000000e+00
> crossprod(Q)
              [,1]          [,2]
[1,]  1.000000e+00 -5.551115e-17
[2,] -5.551115e-17  1.000000e+00

- Schur complementはdeterminantの分解に使える。 $A= \begin{pmatrix}A_{11} A_{12}\\ A_{21} A_{22} \end{pmatrix}$ のとき $detA = (detA_{11}) det(A_{22} - A_{21}A_{11}^{-1}A_{12})$ 。さらに逆行列もSchurの逆行列を使って分割して計算できる
- Cauchy-Binet formulaは、非正方行列の積である行列のdeterminantを積の要素行列のminorのdeterminantの積の和に分解する。 $det(AB) = \sum det A[\{1,....,m\}|S] det B[S|\{1,...,m\}]$
1.2 Eigenvalues of symmetric matrices
- は特性多項式
  - $det(A-\lambda I ) = \prod (\lambda_i - \lambda)$
  - 行列 ABと行列 BAの固有値は多重度を除けば同じ
  - $det A = \prod \lambda_i$ , $trace A = \sum \lambda_i$
- Spectral theorem
  - 対称行列の固有値は実数で、直交行列によって固有値分解できる $PAP' = diag(\lambda)$
  - AB=BAなる対称行列A,Bは、同じPによって固有値分解できる
- 正定値行列
  - 任意の非ゼロベクトル xで $x^T A x > 0$ あるような行列Aが正定値行列
  - 固有値がすべて正で、A=BB' (Bはcull column rank)と分解できて、A=TT' (Tは対角成分が正の下三角行列)に分解できる
  - 半正定値行列はA=B^2(Bも半正定値行列)と分解できる
- Interlacing for eigenvalues
  - 元のnxn正方行列とその(n-1)x(n-1) Principal submatrixには、固有値(元の行列とPrincipal submatrixの固有値を $\lambda, \mu$ とする)について、次の関係がある。 $\lambda_1 \ge \mu_1 \ge \lambda_2 \ge \mu_2 ... \lambda_{n-1} \ge \mu_{n-1} \ge \lambda_n$
  - $A=B + x x^T$ なる行列を取ると $\lambda_1 \ge \mu_1 \ge \lambda_2 \ge \mu_2 ... \lambda_{n-1} \ge \mu_{n-1} \ge \lambda_n \ge \mu_n$ となるという
  - $\lambda_1(A) = max_{||x|=1} x^T A x$ , $\lambda_n(A) = min_{||x||=1} x^T A x$
1.3 Generalized inverses
- $AGA=A$ のとき、GをAのgeneralized inverseという
- singular 行列には、generalized inverse matricesが無限にある
- Moore-Penrose inverseはそのうちの一つ。 $AGA=A,GAG=G,(AG)^T = AG, (GA)^T = GA$
1.4 Graphs