CMT 시험대비

1. 용어

K_n, K_(n,n), K_n^o,

K_n^*

SS

incidence matrix for the configuration {X1,X2,...,Xm} of n-set X(mxn (0,1)-matrix), a seq of m distinct elements of X is a SDR

partly decomposable, fully indecomposable

reducible matrix, irreducible matrix, nearly reducible

totally unimodular matrix

nnn irreducible matrix중

primitive matrix

exponent

imprimitive matrix

index of imprimitivity

Adjacency(multigraph에서 생각, multiple edge개수가 entry로 들어감)

(0,1)-incidence

(0,1,-1)-incidence(orient는 내맘대로)

Adjacency(digraph에서 생각, multiple arc개수가 entry로 들어감, from row to column)

minimally strong digraph

index of imprimitivity of a strongly connected digraph

tourment

permanent(rectangular에서는?)

σ_k(A)

affine set, dimension of nonempty affine set, hyperplane, affine hull

convex hull, convex polytope, dimension of convex set

DQSMT

DSMT, elementary DSMT

SSMT

OSMT

Ω_n, Ω_n(D) where D:fully indecomposable (0,1)-matrix

DSSMT

DSPSMT

RSMT

CSMT

α=an, β=bn

α < β,majorization

α <_w β, weakly submajorized

α <^w β, weakly supermajorized

Ω_n(α<β)

preordering and partial ordering

A is a subset of R^n, f:A->R일 때

A:symmetric이란?

f가

Schur-convex on A

strictly Schur-convex on A

Schur-concave on A

strictly Schur-concave on A

kth-symmetric function, S_k

S=[n], Latin rectangle of S, Latin square of S, reduced Latin square of S

L_n:the number of Latin square of [n]

quasigroup, loop

partial transversal of size t of a Latin square A on [n], transversal of A

2. 정리

About affine, convex

affine set <-> Linear system's solution Ax=b

About Nearly reducible matrix

A:nearly reducible (1,0)-MT일 때

te P and 1<=m<=n-1 s.t. PAP^t = ...

About permutation

P-chain of [n]으로 permutation구하기

about PAP^T

불변량:n-digraph에 labeling만 영향(adjacency matrix A), egv

about PAQ

(n,n)-bipartite에 labeling만 영향, rank

A:invertible 이고 PAQ:LMT iff te! 1-factor of nonzero weight in the weighted bipartite graph associated with A

About det

det(MT(nxn))를 weighted bipartite graph로 표현하기

det(MT(nxn))를 weighted digraph로 표현하기(loop도 포함, 조심)

det(MT(nxn))를 n개의 rectangular MT의 곱으로 표현하기

If MT:PSD, then det(MT) <= prod over all diagonals of MT

About per

per(MT(nxn))를 n개의 rectangular MT의 곱으로 표현하기

per(PAQ)=per(A)

per((A)^t)=per(A)

Laplace Expansion Theorem for permanent(for mxn matrix, choose r, α)

per(A+B)=...

(Frobenius-Konig Theorem), A:nnn nxn MT일 때 per(A)=0 iff te P,Q s.t. PAQ=... sxt, s+t=n+1

(Alexandrov-Egorycev Inequality)If A:nnn, then (per(A))^2 >= ... (if t column빼고 다 positive columns, then = holds iff t는 q column의 multiple)

If per(A(i|s))=per(A(i|t)) for any 1<=i<=n and some s,t, then per(B)=per(A), where B=A except for s,t column은 A의 s,t column의 평균

If A:CSMT s.t. 0<per(A)<=per(A(i|j)) for any i,j, then per(A(i|j))=per(A) for any i,j

About subpermanents, some conjectures

If A:nnn, all row sum<=1, then σ_k(A) <= nCk

(Tverberg)If A:DSMT, then σ_k(A) >= σ_k(J_n) for k=1,2,...,n, with = iff A=J_n

(Dokovic)A:DSMT일 때 σ_k decreases at A on the segment joining A to J_n.(거짓, 1999, Ian)

(Dittert)A:nnn, all entries sum=n, f(A):=prod rowsum + prod colsum - per(A)일 때 f(A) <= 2 - n!/n^n with = iff A=J_n

(Cheon and Hwang)A:nnn, all entries sum=n, f_k(A):=...

About egv

Gershigorin theorem

About Irreducible MT

irreducible 판정:n-digraph가 strongly connected

Frobenius normal form of any matrix A, PAP^t

Frobenius form of irreducible A with index of imprimitivity k, then PAP^t ...

invariant operation of irr:

-transpose

-product? NO

-addition? NO

Perron-Frobenius Thm의 내용(positive일때랑 nnn irreducible일때의 차이는 spectral circle상 egv개수뿐)

About imprimitivity

M:nnn irreducible일 때

M:primitive iff M^m:positive(M:irreducible없어도 됨)

M:primitive iff lim m->inf (M/r)^m exists, limit값은?

imprimitive of M = gcd of the lengths of directed cycles in n-digraph.(index of M = index of D(M))

index of M=k일 때

k개의 egv는 x^k=r^k인 복소수 근들이다.

k_i = k, where k_i:the gcd of lengths of all cycles of D(M) through vertex i

About exponents of primitive MT((0,1)-MT만 다뤄도 됨, 이하 모두 (0,1)-MT)

If M:primitive with p개 nonzero diagonals, then exp(M) <= 2n - p -1

If M:primitive with n개 nonzero diagonals, then exp(M) <= n - 1

If M:primitive and symmetric, then exp(M) <= 2n - 2 with = iff te P s.t. PMP^t = ...

If M:primitive, then exp(M) <= (n-1)^2 + 1 with = iff te P s.t. PMP^t = ...

About Incidence, Adjancecy

About graph, A:(0,1)-incidence, B:Adjacency, C:(0,-1,1)-incidence

(A)^t * A = B + D

(C)^t * C = B - D

If G:connected, then rank(C)=n-1

About DSMT and Majorization

About DQSMT

A:DQSMT iff 1:egv for A with (1,1,1...,1) eigenvector

About DSMT

A:each row sum = each column sum = 1이면 A:square

A:DSMT iff AJ=JA=J, J=[1/n] iff for any x in R^n, Ax < x (majorization)

DSMT1*DSMT2 is also DSMT

per(DSMT) > 0

(Schur)H:hermitian, then te SSMT s.t. h=SSMTλ, h:diagonal entries로 구성된 vector, λ는 egv로 구성된 vector(증명도)

if A:DSMT and reducible, then te P s.t. PAP^t=the direct sum of DSMTs

if A:DSMT and irreducible with index k, then k|n and te P s.t. PAP^t = ... all blocks are (n/k)-square and DSMT

(Birkhoff)Ω_n={all DSMT}=closed bounded convex polytope, dim=(n-1)^2, whose vertices n! permutation MT of order n

D:nxn fully indecomposable (0,1)-MT일 때

Ω_n(D):={all DSMT s.t. DSMT<=D}, called the face of Ω_n, which is a subpolytope of Ω_n

dim(Ω_n(D))=the number of 1 in D - 2n + 1

the number of vertices = per(D)

the barycenter of Ω_n(D) is 1/per(D) sum over P<=D P(P:permutation MT)

About Minimizing

A:minimizing이면

fully indecomposable

if a_(h,k)>0, then per(A(h|k)) = per(A)

(London-Minc)for any i,j, per(A(i|j)) >= per(A)

if 1st row of A and 2nd row of A have the same zero pattern, then per(A)=per(A'), A'의 1,2row는 A의 1,2row의 average로 replaced

if A:positive, then per(A)=per(J_n)=n!/n^n

if A != J_n, then all its zeros cannot occur in a single row(column)

(Egorycev)per(A(i|j))=per(A)

(Alexandrov-Egorycev Inequality)에서 = 성립 for any q,t(q != t)

per(A)=per(A'), A'의 i,j row는 A의 i,jrow의 average로 replaced

(van der Waerden)If A:DSMT, != J_n, then per(A) > per(J_n)

if A:positive DSMT sufficiently close to J_n and A != J_n, then per(A) > per(J_n)

About DSSMT

A:DSSMT

iff te DSMT s.t. A<=DSMT

iff A:nnn and Ae <= e and eA <= e

iff A:nnn and αA <_w α for all nnn α.

{all DSSMT}=convex hull of {M s.t. M has at most one 1 in each row and each column}

About DSPSMT

A:DSPSMT 이면 all row sums and column sums are at least 1(역은 성립 안함)

{all DSPSMT}=convex, not convex hull of its extreme points(extreme points가 permutation matrices뿐)

About Majorization

α < β with nnn

iff (Muirhead) using c and per

iff (HLP) using DSMT

α <_w β with nnn

iff te DSSMT s.t. α = DSSMTβ

α <^w β with nnn

iff te DSPSMT s.t. α = DSPSMTβ

About Schur-convex function on A, A:symmectric and convex subset of R^n, f:A->R, g:R->R

직접 Schur-convex보이기, 단, n=2일때만 보여도 충분

f:C1 on int(A) 일 때 f:Schur-convex on A iff f:symmetric and Schur-condition

f:symmetric and convex이면 f:Schur-convex

f:inc and Schur-convex and g:convex이면 f(g)는 Schur-convex

f:dec and Schur-convex and g:concave이면 f(g) 는 Schur-convex

f:Schur-convex이고 g:inc이면 g(f)는 Schur-convex,

f:Schur-convex이고 g:dec이면 g(f)는 Schur-concave.

대표적인 Schur-convex

sum 1/x_i

sum x_i

sum (-log(x_i))

대표적인 Schur-concave

S_k(k=1,2,...,n)

symmetric, inc, Schur-concave

(S_k)^(1/k):symmetric, inc, concave, Schur-concave

(S_k)/(S_(k-1)):symmetric, concave, Schur-concave

Note)

<_w인 경우 order-preserving의 경우는

f:order-preserving

iff 0>=f_x1>=f_x2>=...>=f_xn for all z in A(f가 C1일 때)

iff f:inc and Schur-convex

<^w인 경우 order-preserving의 경우는

f:order-preserving

iff f:dec and Schur-convex

About Latin squares

L_n = n!(n-1)!R_n, where R_n:the number of reduced Latin squares of [n]

quasigroup on [n] <-> Latin square, bijection

K_(n,n)의 edge coloring(adjacent edges는 다른 coloring, color set=[n]) <-> Latin square, bijection

M_i:=same color perfect matching

transversal of Latin square <-> differenct color perfect matching

|G|=odd이면 {(g)^2|g in G} = G(i.e. all element of G has a unique square root)

따라서 cayley table for a group with odd order의 diagonal은 transversal가 된다.

3. 다시봐야할 것들

αP <^w α for all nnn α이면 P는 DSPSMT인가?