ㅇㅇ

1. 용어

f_n:seq from {0,1,2,...}->F

f(t):fps from {f_n}, :=G[f_n]

f(t,w):fps from {f_(n,k)}, bivariate formal power series from {f_(n,k)}

[t^n]f(t)

ord(f(t))

bar(f(t))

F[[t]], F_k[[t]]

L, laurent power series, 원소는 l(t)

(x)_k, falling factorial

[x]_k, rising factorial

(d(t),h(t))가 pRa

M(d(t),h(t)), riordan array

renewal array

R, riordan group

A, Appell subgroup

Lag, Lagrange subgroup

derivative subgroup, {M(h'(t),h(t)) s.t. h(t) in F_1[[t]]}

2. 정리

About F[[t]]

ord(f(t)+g(t)) >= min{ord(f(t)), ord(g(t)))

ord(f(t)g(t)) = ord(f(t)) + ord(g(t))

(F[[t]],+,*):ID, quotient field는 L

About F_0[[t]]

(F_0[[t]], *):abelian group((F_0[[t]], +, *)에서는 +에 대해 닫혀있지 않음)

About F_1[[t]]

(F_1[[t]], o):group

About L

[t^n]의 성질 중 f(t)g(t)와 f(g(t))와 bar(f(t))에 관해서 복습, 특히 마지막을 Lagrange Inversion formula([t^n]bar(f(t)), [t^n]{bar(f(t))}^k)

About riordan array, riordan group

R:group

M(d(t),h(t))*M(a(t),b(t))=M(d(t)a(h(t)),b(h(t))), riordan arrays are closed under the matrix product

multiplicative identity는 M(1,t)

M(d(t),h(t))의 multiplicative inverse는 M(1/d(bar(h(t)), bar(h(t)))

Every pRa can be seen as the product of an Appell by a Lagrange matrix

{f_(n,k)}:pRa iff te d(t) in F_0[[t]] and h(t) in F_1[[t]] s.t. f(t,w) = d(t)/{1-wh(t)}

pRa is characterized by d_(0,0), Z-seq, and A-seq

About functional equation w(t)=tΦ(w(t))

Φ in F_0[[t]] and F in F_0[[t]]일 때

[t^n]w(t) = 1/n * [t^(n-1)](Φ(t))^n, n>0

[t^n](w(t))^k = k/n * [t^(n-k)](Φ(t))^n, n>0

[t^n]F(w(t)) = 1/n * [t^(n-1)]F'(t)(Φ(t))^n = [t^n](F(t) * (Φ(t))^(n-1) * (Φ(t)-tΦ'(t)))

f(t), g(t) in L

[t^(-1)]f(t)g'(t) = - [t^(-1)]f'(t)g(t)

Φ in F_0[[t]] and F in F[[t]]일 때

(Diagonalization rule) {c_n}={[t^n]F(t)(Φ(t)^n)}의 generating function은 F(w)/(1-tΦ'(w)), w=tΦ(w)

F and Φ and φ in F_0[[t]]일 때

[t^(n-k)]F(t)(φ(t))^n(Φ(t))^k M(d(t),h(t)), where d(t) = F(w)φ(w)/(φ(w)-wφ'(w)), h(t)=wΦ(w), w=tφ(w)

About A-seq and B-seq and Z-seq of pRa, given pRa(=M(d(t),h(t))

About A-seq

An infinite lower triangular array D is pRa iff te A-seq of D(a_0 != 0)

(->방향은 M(d(t),h(t))에서 M(d(t),h(t))*M(A(t),M(t)) = M(d(t)h(t)/t, h(t))이용해서 M(t)=t보이고 좌우변 generic element비교)

(<-방향은 h(t)=tA(t) 이용해서 h(t) 구하고 d(t)는 D의 0-column읽어서 구함)

Given pRa, A-seq의 generating function바로 구하는 법, A(t)=t/bar(h(t)), A(y)=h(t)/t, y=h(t)

About B-seq

Given pRa, te B-seq(M(d(t),h(t))=M(d(t)h(t)/t, h(t))*M(A(t),t)^(-1)을 이용해서 구함, B(t)=(A(t))^(-1)임)

About Z-seq

Given pRa, te Z-seq

(z_0 = d_(1,0)/d_(0,0), d_(2,0)=z_0 * d_(1,0) + z_1 * d_(1,1)해서 z_1구하고 이런 방식으로 쭉 구함)

Given pRa, Z-seq의 generating function(implicit), d(t)=d_(0,0)/(1-tZ(h(t))), 따라서 Z(y)=(d(t)-d_(0,0))/(td(t)), y=h(t)

About renewal array

a pRa M(d(t),h(t)) is renewal array

iff d(t)=h(t)/t

iff A(y)=d_(0,0) + yZ(y) and d(0)=h(0) != 0

A:Appell subgroup

A:normal in R

Lag:Lagrange subgroup

L:subgroup in R

L giso (F_1[[t]], o)

3. 요약

P=M(1/(1-t), t/(1-t))의 경우 generic element가 계산 쉬움, binomial formula쓰면 됨

C=M(1/sqrt(1-4t), (1-sqrt(1-4t))/2)의 경우 generic element를 guess한 다음, [t^n]~~꼴로 써넣고 보니 n이 포함된 형태, 따라서 diagonalization rule사용하여 증명

4. 문제들

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 = ...

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인가?

Chapter 1 What is CMT?

*Def

walk

path(walk와의 차이는 distinct vertices)

connected graph

matching, k-matching, matching number

vertex-cover, cover number

K_n, complete graph

K_no, complete graph with all loops

K_n*, complete digraph with all loops

G(MT), called the Konig digraph

IcMT(configuration of X)

MT(nxn):reducible or irreducible

nnn irreducible중에서

primitive MT

the exponent of primitive MT?

imprimitive MT, 이경우 index of imprimitivity 정의
G1,G2:cospectral if spec(A(G))=spec(A(G'))

IcMT(G), (1,0) matrix

*Thm

Principal tools of Combinatorics

-Mathematical Induction

-Pigeonhole Principle

-Inclusion-Exclusion Principle

-The methods of recurrence relations and generating functions

-Graph Theory

-Burnside's Theorem

-Polya Enumeration Theorem

각각 내용 알기, 특히 Exponential Generating Functions관련해서 내용정리 추가 필요

Tree의 equivalent def

-connected acyclic

-for distinct u,v in V(G), te! path from u to v

-connected with n-1 edges

-connected and removing any edge makes G disconnected

G:bipartite이면 cover number = matching number

From Matrix to graph

no need square(invariant for PAQ, like rank)

MT(mxn) -> K_(m,n)의 subgraph, ker(MT), bar(ker(MT)), bar(ker(MT))의 경우 weigted로도 볼 수 있는데 그 경우 bar(ker(MT))에서 0는 no edge로 보면 됨

MT(mxn) -> G(MT), K_(m,n)의 digraph 형태, weight있는 경우

MT(nxn)의 경우 그냥 G(MT)보고 det(MT)를 wt(all 1-factors)로 묘사가능

square(invariant for PArt(P), like egv)

SMT(nxn) -> K_no의 subgraph, ket(MT), bar(ker(MT)), weighted로도 볼 수 있음, bar(ker(MT))에서 0는 no edge로 보면 됨

MT(nxn) -> K_n*의 subgraph, ker(MT), bar(ker(MT)), weighted로도 볼 수 있음, bar(ker(MT))에서 0는 no edge로 보면 됨

From (di)graph to matrix

(1,0)-A(G)

arc가 있냐 없냐로 1,0

det(A(G))=(-1)^n * wt(D_n),

where D_n:={all 1-factor of σ, σ in S_n},

wt(D_n)=sum over all σ wt(F_σ),

wt(F_σ)=sign(σ) * prod over all i=1 to i=n a_(i,σ(i))

따라서 (di)graph의 형태를 보고 det구할 수 있다. cycles

A(G)^k의 (i,j)원소의 의미는 the number of walks of length k from i to j

IcMT(G)

rt(IcMT(G))*IcMT(G) = sLap(G)

det, perm using IcMT

det(MT(nxn))=W^1 W^2 ... W^n, W^i:(n choose i-1)x(n choose i) using (i+1)th row element in MT

perm(MT(nxn))=W^1 W^2 ... W^n, W^i:(n choose i-1)x(n choose i) using (i+1)th row element in MT

Perron Theorem for positive MT

About irreducible

MT:irreducible

iff G(MT):strongly connected, (G(MT):K_n*의 subgraph, unweighted directed)

About primitive MT

the index of imprimitive = gcd(the lengths of all directed cycles in G(MT))

MT:primitive

iff lim m->inf (MT/specR(MT))^m exists, the limit = (p*rt(q))/(rt(q)*p) > 0, where p:perron for MT, q:perron for rt(MT)

iff the index of imprimitive = 1

iff gcd(the lengths of all directed cycles in G(MT)) = 1, (G(MT):K_n*의 subgraph, unweighted directed)

iff MT^m > 0 for some m, called the exponent

Perron-Frobenius Theorem for irreducible NNN MT

Discriminative Model

-P[input, C_i], P[C_i]는 관심없고 P[C_i|input]만 modeling, learning하여서 P[C_i|input]을 구하여서 Classification

-특징

-SVM, Logstic regression 등 

Generative Model

-P[C_i], P[input, C_i] 혹은 P[C_i], P[input|C_i]을 modeling, learning하여서 P[C_i|input]을 구하여서 Classification

-특징

-HMM, GMM 등

1. Prior만 있을 때(P[Ci])

주어진 것:개와 고양이의 비율(0.6과 0.4)

문제:수영이네 애완동물이 개냐 고양이냐?

->개로 선택하는 것이 가장 best, error는 항상 0.4

2. P[Ci]와 P[Observation|Ci]가 주어졌을 때

주어진 것:개와 고양이의 비율, 어떤 개가 가지는 키의 분포, 어떤 고양이가 가지는 키의 분포

문제:수영이네 애완동물의 키가 k일때, 그 동물이 개냐 고양이냐?

->P[개|k]와 P[고양이|k]중 큰 것을 고르는 게 best

3. Loss Function(=cost function) 설정

L(true parameter, estimated parameter from input)을 최소화하고 싶지만

input으로만으로 true parameter을 모르므로, expectation of L을 최소화하자. 

근데 그것 또한 expectation of L given input을 최소화 하는 것과 동치이므로 expectation of L given input을 최소화 하자.

이렇게  expectation of L given input을 최소화시키는 estimator for parameter from input을 bayes estimator라 한다.

Loss function을 어떻게 설정하냐에 따라 Bayes Estimator의 형태가 달라진다.

Chapter 1 Hilbert Space

*용어정의

1. vector space의 semi-inner product란? inner product란?

2. Hilbert space의 정의

3. Absolutely continuous for f:[a,b]->F의 정의와 동치 2가지

4. G:open in C일 때 the bergman space for G란?

5. perp(E)의 정의, projection of a closed linear subspace(P_K)의 정의

6. S:subset of HS, VS란?

6. bdd linear functional f:HS->F의 정의

7. basis for HS의 정의

8. infinite subset S of HS가 linearly independent란, any finite subset of S가 linearly independent

9. dimension of HS란?

10. HS1,HS2:isomorphic이란 linear, surjective, preserve ip map이 존재

11. f:MetricS1->MetricS2가 isometry란?

12. f:HS->HS가 unitary operator란?(isomorphism인데 정의역=공역)

13. direct sum of HS1,HS2란?direct sum of countable HS_i란? direct sum of HS_i란?(net)

*Thm

1. CBS inequality and equality iff there are scalar a,b(not both 0)...

2. Absolutely continuous for f:[a,b]->F의 성질

-+,-,*,/에 닫혀있다.

-Lipschitz Continous이면 Absolutely Continuous이다.

-Absolutely Continuous이면 Uniformly Continuous이다.

3. Completion of IPS(extention of <,>, norm, and metric)

4. Polar Identity란

5. if K:closed convex, then dist(h_o,K)=d(h_0,k_0)인 k_0 in K존재 and unique

6. if K:closed linear subspace, then dist(h_0,K)=d(h_0,k_0)인 k_0 in K존재 and unique and h_0 - k_0:orthogonal to K

7. if K:closed linear subspace and h_0 - k_0:orthogonal to K인 k_0 in K 존재, then dist(h_0,k_0)=d(h_0,k_0)

8. perp(E):closed linear subspace of HS

9. projection of a closed linear subspace(P_K)의 성질

-linear

-norm<=1

-idempotent

-ran(P_K)=K, ker(P_K)=perp(K)

10. K:closed linear subspace of HS이면 perp(perp(K))=K

11. perp(perp(E))=closed linear span of E

12. S:linear subspace of HS일 때 S:dense in HS iff perp(S)={0}

13. f:HS->F, linear, TFAE

-conti, uniformly conti, conti at 0, conti at any pt, bdd

14. (Riesz for HS)f:HS->F, linear, bdd일 떄 f(h)=<h,h_0>인 h_0가 유일하게 존재 with ||f||=||h_0||

15. (Gram-schmidt) S:linearly ind이면 S':orthonormal s.t. ....

16. S:finite orthonormal일때 projection of VS의 representation

17. (Bessel)S:countable orthonormal일때 sum of (coefficients)^2 <= ||h|| 

18. S:orthonormal일때 sum of (coefficients)^2 <= ||h||(net)

19. net으로 cv이면 걍 cv

20. S:orthonormal일때 sum of <h,s>s는 always cv(net)

21. S:orthonormal일때 TFAE

-S:basis

-hㅗS이면 h=0

-VS=HS

-h=sum of <h,s>s(net)

-<h1,h2>=sum of <h1,s><s,h2>(net)

-(Parseval's Identity)||h||=sum of ||<h,s>||^2(net)

22. S1,S2:basis then, |S1|=|S2|

23. HS:separable iff dim(HS):at most countable

24. f:HS1->HS2가 linear일때 f:isometry iff f:preserve ip

25. f:HS1->HS2가 linear, isometry일 때

-ran(f):closed

26. HS1,HS2:isomorphic iff dim(HS1)=dim(HS2)

-HS with basis S, HS와 l^2(S)는 isomorphic

(Fourier는 따로 보고, 보고나서는 Chapter2, Example 4.12보기)

Chapter 2 Operators on Hilbert Space

*용어정의

1. B(HS1,HS2)란?

2. M_Φ란?

3. k:MSxMS->F, measurable, K:integral operator란?

4. u:HS1xHS2->F, sesquilinear란? sesquilinear가 bdd란? 대표적인 bdd sesquilinear는?

5. f in B(HS1,HS2)일 때, adj(f)란?

6. f in B(HS1,HS2)가 invertible이란?

7. f in B(HS)가 hermitian이란?, normal이란?

8. f in B(HS)가 idempotent란?, projection이란?(of a closed linear space란 거 없이)

9. K_i:closed linear subspace of HS일 때 the direct sum of K_i란?

10. f in B(HS)에 대해 invariant subspace for f란?(closed필요), reducing subspace for f 란?(closed필요)

11. f in B(HS)에 대해 f:compact란?

12. B_0(HS1,HS2)란?

13. f:HS->HS가 finite rank를 가진다란?

14. B_00(HS1,HS2)란?

*Thm

1. f:HS1->HS2, linear, TFAE

-conti, uniformly conti, conti at 0, conti at any pt, bdd

2. B(HS1,HS2):NVS

3. f in B(HS1,HS2), g in B(HS2,HS3), then g o f in B(HS1,HS3)

4. u:sesquilinear, bdd이면 u(h1,h2)=<Ah1,h2>=<h1,Bh2>인 A:HS1->HS2, B:HS2->HS1, linear, bdd가 유일하게 존재

5. f in B(HS1,HS2)일때 f:surjective isometry iff adj(f)=inv(f)

6. about adjoint, f,g in B(HS), a:scalar

-adj(af+g)=conj(a)adj(f)+adj(g)

-adj(gf)=adj(f)adj(g)

-adj(adj(f))=f

-if f:invertible, then adj(f):invertible and adj(inv(f))=inv(adj(f))

-||f||=||adj(f)||=(||adj(f) o f||)^1/2

7. (Consequence of Open Mapping Theorem) f in B(HS1,HS2), bijective이면 invertible이다.

8. f:HS->HS, linear, bdd일때 f:hermitian iff <f(h),h>:real for all h in HS(Base field가 C일 때만 성립)

9. f:HS->HS, hermitian일때

-||f||:=sup over ||h||=1 {|<f(h),h>|}

-<f(h),h>=0 for all h in HS이면 f=0(HS over C이면 f:hermitian조건 없어도 됨)

10. f:HS->HS, linear, bdd일때 TFAE

-f:normal

-||f(h)||=||adj(f)(h)|| for all h

-the real and imaginary parts of f commute(HS over C일 때만)

(real part of f := (f+adj(f))/2, imaginary part of f := (f-adj(f))/2

11. f:HS->HS, linear, bdd일때 TFAE

-f:isometry

-f:preserve ip

-adj(f)f=identity

12. f:HS->HS, linear bdd일 때 TFAE

-adj(f)f=fadj(f)=identity

-f:unitary

-f:normal isometry

13. f:HS->HS, linear bdd일 때

ker(f)=perp(ran(adj(f)))

ker(adj(f))=perp(ran(f))

perp(ker(f))=closure of ran(adj(f))

perp(ker(adj(f))= closure of ran(f)

(perp(ker(f))=ran(adj(f))는 아닐 수 있음, 조심)

14. f:idempotent iff I-f:idempotent

15. if f:idempotent, then ran(I-f)=ker(f), ker(I-f)=ran(f), and HS=the direct sum of ker(f) and ran(f) (여기서 direct sum은 그냥 Vector Space에서의 direct sum)

16. HS=the direct sum of S1 and S2이면 te! f in B(HS) s.t. ran(f)=S1 and ker(f)=S2

17. f:nonzero idempotent이면 TFAE

-f:projection

-f:orthogonal projection onto ran(f)

-||f||=1

-f:hermitian

-f:normal

-<f(h),h)> >= 0 for all h

18. K1,K2:closed linear subspace of HS일때 the direct sum of K1 and K2는 K1+K2와 같다.(finite는 다 됨, infinite는 안됨)

19. K:closed linear subspace of HS일 때 HS=the direct sum of K and perp(K)

20. f in B(HS), K:closed linear subspace of HS, P:projection onto K, TFAE

-K:invariant subspace for f

-PfP=fP

-f:K->perp(K)는 0가 된다.

21. f in B(HS), K:closed linear subspace of HS, P:projection onto K, TFAE

-K:reducing subspace for f

-Pf=fP

-f:K->perp(K)는 0, f:perp(K)->K도 0

-K:reducing subsapce for f and adj(f)

22. f in B(HS), K:invariant closed linear subspace of HS일 때 ||the restriction of f onto K||<=||f||

23. B_0(HS1,HS2):closed in B(HS1,HS2)

24. f in B(HS1), g in B(HS2), T in B_0(HS1,HS2)일 때 Tf in B_0(HS1,HS2)이고 gT in B_0(HS1,HS2)이다.(two-sided ideal)

25. f in B(HS1,HS2)일때 TFAE

-f:compact

-adj(f):compact

-te seq {f_n} s.t. f_n:finite rank and ||f_n - f||->0

26. f in B_0(HS1,HS2)일 때

-cl(ran(f)):separable

-if {e_n}:basis for cl(ran(f)) and P_n:projection onto V{e_j | 1<= j <=n}, then ||P_n o f - f||->0

27. HS:separable with basis {e_n} and {α_n} s.t. sup|α_n|=M<inf일때

-if f e_n=α_n e_n for all n, then f can be extended by linearity to a bdd f with ||f||=M. 그리고 그 f:compact iff α_n -> 0

28. f in B_0(HS), λ:nonzero egv for f일때, eigenspace는 finite dimension

29. f in B_0(HS), λ:nonzero s.t. inf{||(f-λ)h|| over ||h||=1}=0이면 λ:egv for f

30. f in B_0(HS), λ:nonzero, nonegv for f, conj(λ):nonegv for adj(f)이면 ran(f-λ)=HS and inv(f-λ):bdd

Chapter 3 Banach Spaces

*용어정의

1. seminorm on VS란?

2. two norms가 equivalent란?

3. C_b(X)란?C_0(X)란?C^(n)[0,1]이란?

4. NVS1,NVS2가 isometrically isomorphic이란?(linear, surjective, isometry)(그냥 isomorphic하면, linear, bijective, homeo를 가리킴, 즉 topologically iso)

5. direct sum of NVS using finite p, using inf, using cv to

6. hyplerplane of VS란?

7. NVS가 reflexive란?

*Thm

1. two norms가 equivalent iff C1||x||<=|||x|||<=C2||x||

2. B(NVS1,NVS2):BS iff NVS2:BS

3. dim(NVS):finite이면 any two norms on NVS are equivalent

4. any finite dimensional linear manifold is closed in larger one.

5. f:NVS1->NVS2, linear, dim(NVS1):finite이면 f:continuous

6. K:closed linear subspace of NVS이면

-NVS/K:normed vector space

-natural map Q:NVS->NVS/K, linear, conti, open

-if NVS:BS, then NVS/K도 BS

-U:open in NVS iff Q(U):open in NVS/K

7. X:NVS, M:closed linear subspace of X, N:finite dim of X이면 M+N은 closed linear subspace of X

8. direct sum of NVS using cv to 0 is linear subspace of direct sum of NVS using inf

9. X:direct sum of NVS using finite p

-X:NVS and projection onto NVS_i is linear, conti, bdd with 1 norm, open map, surjective

-X:BS iff NVS_i:BS

10. S:hyperplane of NVS이면 S는 dense in NVS or closed in NVS

11. f:NVS->F, linear functional일때 f:conti iff ker(f):closed

12. (NVS)^*:BS(if NVS is nonzero)

13. (Hahn-Banach Theorem)X:VS over R and g:sunlinear functional, S:linear subspace of X, f:linear functional on S s.t. f<=g

then te F:X->R s.t. F=f on S and F<=g

(이 Theorem의 의미는 g에 dominate가 계속 유지되면서 extension을 찾는 것임)

(Lemma6.3부터 Cor6.8까지 읽기)

(Thm 6.13부터 Cor6.14까지 읽기)

14. (Open Mapping Theorem)f in B(BS1,BS2)가 surjective이면 open map

15. (Inverse Mapping Theorem)f in B(BS1,BS2)가 bijective이면 f^(-1)도 conti(bdd)

16. (Closed Graph Theorem)f:BS1->BS2, linear가 closed graph를 가지면 f는 conti

17. (Uniform Boundedness Principle)F:a collection of f:BS->NVS s.t. for any x in BS, sup over f {|f(x)|}<inf이면 sup over f ||f||<inf

*example

1. semi-inner product인데 not inner product인 예?

2. {f:[0,1]->F, f:AC, f(0)=0, f' in L^2[0,1]} with int from x=0 to x=1 f'coj(g')=<f,g>, HS임을 보여라.

3. 걍 cv인데 not net cv인 예?(net cv를 abs cv로 생각하면 예 찾기 쉬움)

4. idempotent인데 not projection인 예 (1 0 1 0) matrix

5. NVS/S가 seminorm은 되는데 norm안되는 예 X=C_0, M=C_00

6. natural map Q:NVS->NVS/K가 not closed map인걸 보이는 예, X=L^2(-pi,pi), M=V{e_n}, F=V{f_n} where f_n(t) = e_(-n)(t) + n*e_n(t), e_n(t)=exp(int)

7. ker(linear functional):not closed in NVS, dense in NVS인 예 X=C_0(N), {e_n(i)=1 for only i=n}, x_0(i)=1/i, then Hamel basis containing {e_1,...,x_0}, make f

*특정 concepts

-L^p with MS, 1<=p<=inf

-BS

-(L^p)^* = L^q

-p=1일땐 sf-M여야 가능

-reflexive for 1<p<inf

-about K with k

-K:L^p(MS)->L^p(MS), linear, bdd, ||K|| <= (c_1)^1/p * (c_2)^1/q

-l^2(I)

-{simple functions}:dense in l^2(I)

-HS

-basis = {e_i s.t. i in I}

-HS with basis S일때 HS와 l^2(S)는 isormophic as HS

-I=N일 때

-unilateral shift

-isometry

-not surjective

-not normal

-backward shift

-adj(unilateral shift)

-l^inf(I)

-I=N일때

-all bdd seq of scalars

-the bergman space for G

-HS(Cauchy, Riesz, Morera Theorems 필요)

-L^2[0,2pi] with C

-HS

-basis = {1/sqrt(2pi) * exp(int) s.t. n in Z}

-L^2(-pi,pi) with C

-L^2 with MS

-about K with k

-K:L^2(MS)->L^2(MS), linear, bdd, ||K||<=(c1*c2)^(1/2), compact operator, ||K|| <= ||k||_2 (L^2 norm)

-adj(K)는 with kernel conj(k(y,x))

-about Volterra, k:[0,1]x[0,1] ->R, char function of {(x,y) s.t. y<x}

-no eigenvalues

-k:L^2(-pi,pi)xL^2(-pi,pi) -> C,

-L^2 with sf-M

-M_Φ in BS(L^2) and ||M_Φ||=||Φ||

-adj(M_Φ)=M_(conj(Φ))

-M_Φ:normal

-M_Φ:hermitian iff Φ:real

-M_Φ:unitary iff |Φ|=1 a.e.

-L^p with sf-M, 1 <= p <= inf

-M_Φ in BS(L^p) with ||M_Φ||=||Φ||

-C_b(X)

-BS

-C_0(X)

-closed in C_b(X)

-X=N일때

-all seq cv to 0

-C^(n)[0,1]

-BS
 

로지스틱 회귀

-종속 변수가 범주형인 데이터를 대상으로 한다.

-독립 변수를 통해 종속 변수값을 얻고 그것을 통해 classification하는데 사용한다.

-즉, (종속, 독립)=(범주,기타)로 regression돌리고, 실제로 사용은 (얻은값, 입력값)을 통해서 classification

-범주의 종류가 2개보다 많으면 multinomial logistic regression이라 한다.

-범주의 종류가 2개보다 많고 순서가 존재하면 ordinal logistic regression이라 한다.

-얻은값의 범위가 [0,1]이기 위해 logsistic function(1/(1+exp(-x))), gumbell function(exp(-exp(x)))등을 합성해서 사용한다.

-계산 편의상 전자를 많이 쓴다.

-1/(1+exp(-~~~~))는 p(y=1|x)를 가리킨다. 즉 독립변수 x가 주어졌을 때, 그것이 y=1(카테고리)일 확률을 가리킨다.

-추정계수를 구하는 건 Maximum likelihood method쓰거나 gradient descent사용

*정의 

1. X:J->R, rdv, f:pdf of X, 이때 Information entropy(or Shannon entropy) of X is defined as H(X):=(-1)*E[ln(f(X))]

(이때 밑이 2인 log를 사용할 경우 단위는 비트이고 자연로그를 사용할 경우 단위는 nat이다.)

(혹은 H(f)라고도 쓴다.)

2. X,Y:J->R, rdv, f,g:pdf of X,Y, 이때 두 분포의 Kullback-Leibler divergence, KLD is defined as 

D_(KL)(f||g) = int from x=-inf to x=inf f(x)*log(f(x)/g(x))dx (Radon-Nikodym derivative를 사용한 것도 있다.위키참조)

3. H(f,g), the cross entropy between f,g, := E[-log(g)] using pdf f

*의의

1.

-H(X) using parameter p1 > H(X) using parameter p2라면, parameter 값이 p1일 때 불확실성이 더 높다는 의미를 가진다. 예를 들면 동전던지기의 경우, 동전의 앞면이 나올 확률이 1/2일 때가 entropy값이 가장 높게 나오고 그때가 불확실성이 가장 높다는 것. 즉 entropy란 불확실성을 정량화한 지표이다.

-H(f)란 f를 묘사하기위해 필요한 불확실성(정보량)을 가리킨다. 

2. 

-D_(KL)(f||g)는 f가 있는데 샘플링 과정에서 그 f를 근사적으로 표현하는 확률분포 g를 f대신에 사용할 경우 엔트로피 변화를 의미한다. 

-따라서 D_(KL)(f||g) = H(f,g) - H(f)

3. 

-H(f,g)란 f를 묘사하기위해  g를 쓸 경우 필요한 정보량(불확실성)을 가리킨다.

-machine learning and optimization에서 사용되기도 하는데, error function(=cost, loss function)으로서 사용한다. 

-예를 들면 logistic regression의 경우, 분류의 실제 분포가 베르누이를 따른다고 하고 (p=P(y=1)), 실제로 우리가 regression을 통해 얻은 분포(g=P(y=1|x), 

이때 H(p,g)=(-p)*log(g) - (1-p)*(log(1-g)), 이값이 작아지도록 regression 계수 추정 가능(대게는 Maximum likelihood method사용하기도 하지만)

-혹은 samples모두 의 H(p,g)의 평균을 줄이는 방향으로 regression 계수 추정하기도 함

*Class of Graphs and their a(G) in terms of graph invariants

K_n

-a(G) = n

K_(a,b)

-a(G) = min(a,b)

P_n

-a(G) = 2 - 2cos(pi/n)

C_n

-a(G) = 2 - 2cos(2pi/n)

W_n

-a(G) = 3 - 2cos(2pi/n)

S_n

-a(G) = 1

S_n^*(K_(1,n-2)의 pendant vertex와 P_2의 한 점을 identifying)

-a(G) < 0.5(직접 characteristic polynomial 구해서)

Q_n

-a(G) = 2

X(Z_n,C)

-C={1,n-1}

-a(G) = 2 - 2cos(2pi/n)

-C={1,2}

...

J(v,k,i)

-v>=2k, i=(k-1), johnson,

-v>=2k, i=0, kneser

-J(5,2,0), petersen, a(G) = 2

CS(n,w)

-a(G) = n - w

PA(n,w)

-a(G) = 1

Ki(n,w)

ST(a,b)

T(n,a,b)

multipartite

split graph

difference graph

cograph

threshold graph(=maximal graph)

r-regular

(r,s)-semiregular

caterpillar, CTPL

binary tree

------------------------------------------------------------------------------------------------------------------------

*Graph Invariants

V와 V의 subset의 개수

n

τ(G)

γ(G)

α(G)

p(G)

q(G)

E와 E의 subset의 개수

m

Τ(G)

ν(G)

degree관련

δ(G)

d(G)

Δ(G)

1-Zagreb(G)

2-Zagreb(G)

decdseq(G)

tr(G)

path, length관련

r(G)

D(G)

md_G

d(G,k)

W(G)

H(G)

TW(G)

HW(G)

RCW(G)

MTI(G)

DD(G)

topological관련

genus(G)

subgraph관련

sd(G)

g(G)

G(G)

ω(G)

t(G)

Tree관련

Type 1 or Type 2

Connectivity관련

connectivity

# of components

cutvertex

bridge

κ(G)

λ(G)

Color관련

χ(G)

Homomorphism관련

Aut(G)

------------------------------------------------------------------------------------------------------------------------

*Related bounds for a(G), G:connected

a(P_n) <= a(G) <= n (Fiedler 1973)

a(G)<=κ(G)<=λ(G)<=δ(G), (Fiedler 1973)(G:K_n일땐 성립안할 수 있음, 조심)

처음 <은 path생각, 두번째 <은 triangle 2개를 1개꼭지점을 common, 세번째 <은 T1(a,b)에다가 양 끝에 path을 attach한 것

처음 = iff G=G1VG2, where G1:disconnected of order n - κ(G), G2:of order κ(G) with a(G2) >= 2 * κ(G) - n (Kirkland, Molitierno, Neumann and Shader 2002)

if G:not K_n, then a(G) <= [[-1 + 2 * sqrt(1 + 2 * m)]] (Belhaiza, Abreu, Hansen and Oliverita 2005)

a(G) >= 4/(n * D(G)) (Mohar 1992)

a(T) <= 2 * (1 - cos(pi/(D(T)+1))) (Grone, Merris and Sunder 1990)

if T:planar, then a(G) <= 4, with = iff G=K_4 or K_(2,2,2)

if n >= 6 and G:non-isomorphic to K_n, then a(G) < 0.49

a(G) <= a(P_(D(G)+1))

2*cos(pi/n - cos(2pi/n))*κ(G) - 2*cos(pi/n * (1-cos(pi/n)))*Δ <= a(G)

------------------------------------------------------------------------------------------------------------------------

*Main Theory of matrix, or Fiedler vector, etc

y_i = 0 and i~j and y_j > 0이면 te k s.t. i~k and y_k < 0

y_i > 0이면 te j s.t. i~j and y_j < y_i

v:cut vertex, G - k = G_0+G_1+...+G_r일 때

y_k > 0이면 te! G_j s.t. contains a vertex(vertices) with negative valuation이고 나머지 components의 y값은 y_k보다 큼

y_k = 0이고 te G_j s.t. containing both positive and negative이면 te! G_j이고 나머지 components는 다 0

y_k = 0이고 te no G_j s.t. containing aboth positve and negative이면 각 G_k들은 모두 only positive or only negative or only zero

(y_k < 0인 경우도 결국 설명됨, eigenvector니까)(Fiedler 1975)

G:connected with at least one cut vertex일 때 다음 2가지 중 1가지는 반드시 성립(Fiedler 1975)

(a)

te! B0 in which contains both positively and negatively.

Each other block has either vertices with positive only, negative only, or zero only

Every pure path P starting at B0 and containing just one vertex k in B0 has the property that the valuations at the cut vertices contained in P form either an increasing, decreasing, or zero sequence along this path.(pure path란 각 block의 articulation을 0,1번만 지나는 path)

a(G) is simple

(b)

No block of G contains both positive and negative.

te! j which has zero and is adjacent to a nonzero and j is a cut vertex.

Each block contains either positive only, negative only, or zero only.(zero랑 positive가 같이 있는 경우도 없는!)

Every pure path P starting at j has the property that the valuations at the cut vertices contained in P form either an increasing, decreasing, or zero sequence along this path.

the induced subgraph from zero is connected

위의 내용을 Tree에 적용하면(Fiedler 1975)

(a)

all valuations are nonzero

te! ij s.t. yi >0 and yj < 0

any path from i not containing j 는 increasing concave down(위로 볼록)

any path from j not containing i 는 decreasing concave up(아래로 볼록)

a(G):simple

(b)

te! i s.t. yi = 0 and i is adjacent to nonzero

any path from i 는 increasing concave down(위로볼록), decreasing concave up(아래로 볼록), or identically zero.

T:tree일 때

L_k:invertible,

inv(L_k)_(i,j) = sum over all edge in P_(i,j) 1/w(edge)

, where P_(i,j):the set of edges of T which are simultaneously on the path from i to k and on the path from j to k, w:weight

inv(L_k) permutationally similar to a block diagonal matrix in which each block is positive and correponds to a branch at k.(즉 Lap(T)에서 branch에 해당하는 submatrix의 inverse가 됨)(Kirkland, Neumann, Shader, 1996)

T:tree일 때

T:type I with characteristic vertex k iff te two or more Perron branch of T at k.

Moreover, a(T) = 1/specR(inv(L_k)), where L_k:Lap(G)에서 kth row와 kth column제거한 것. (Kirkland, Neumann and Shader 1996)

T:tree, i~j일 때

T:type II with characteristic vertices i,j iff te 0 < eps < 1 s.t. specR(M1 - eps * J) = specR(M2 - (1 - eps) * J)

Moreover, a(T) = 1/specR(M1 - eps * J) = 1/specR(M2 - (1 - eps) * J) and the branch at i containing j is the unique Perron branch at i and the branch at j containing i is the unique Perron branch at j

where M1:bottleneck matrix for the branch at j containing i, M2:bottleneck matrix for the branch at i containing j. (Kirkland and Neumann 1997)

T:tree일 때

T:type I iff te! i s.t. te two or more Perron branches at i

T:type II iff for any i, te! Perron branch at i(Kirkland, Neumann and Shader 1996)

T:tree type I with characteristic vertex i이고 am(a)=k이면 i has exactly k+1 Perron branches(Grone and Merris 1987)

T:tree, i:non-characteristic vertex이면 te! Perron branch at i and the branch contains all of the characteristic vertices of T(Kirkland, Neumann and Shader 1996)

For positive integers k1,k2,...,km, form an tree T by taking a vertex x and making it adjacent to the root vertices of both T(k1,k2,...,km) and T(km,...,k1). Then T is a type I tree with characteristic vertex x.

where T(k1,k2,...,km):한 vertex x에서 k1개 pendant붙이고 각 pendant에 k2개 pendant붙이고...km까지(Kirkland 1999)

T:tree, B:branch at i which does not contain all of the characteristic vertex(vertices) of T. Form T' from T by replacing the B by some other branch B' at i.

M:the bottleneck matrix of B, M':the bottleneck matrix of B'

if M << M', then

a(T') <= a(T)

the characteristic vertices of T' are either on the path joining the characteristic vertices of T to i, or they are located on B'(Kirkland, Neumann 1997)

(A << B means te P,Q s.t. P:Permutation MT, Q:permutation MT, if the order of A < the order of B, PArt(P) is entrywise dominated(<=) by a psubMT of QBrt(Q), if the order of A = the order of B, PArt(P) is entrywise dominated by QBrt(Q) with at least one strictly inequality)

the corollaries

위의 내용을 adding a pendant vertex로 보면

a(T') <= a(T)

the characteristic vertices of T' lie on the path between the characteristic vertices of T and the new pendant vertex.(Kirkland, Neumann 1997)

위의 내용을 change B to path로 보면

Form T' from T by replacing B(the order of B is k) by P_k with i adjacent to the end of P_k, then

a(T') <= a(T)

위의 내용을 change B to star로 보면

Form T' from T by replacing B(the order of B is k) by K_(1,k-1) with i adjacent to the center of the star, then

a(T) <= a(T')

위의 내용을 subtree인 경우를 보면

Any subtree T' of T, a(T') <= a(T)

T:type I with characteristic vertex i, d(i)=d, B1,B2:Perron branches, B3,B4,...,Bd:other branches, |B3UB4U...Bd|=k

Let H:any graph on k vertices

Form G from T by discarding B3,B4,...,Bd and adjoining i to some or all vertices of H.

Then a(G) <= a(T) (Grone and Merris 1990)

------------------------------------------------------------------------------------------------------------------------

*Graph Perbutation and related theorems

G -> G'=L(G)

G -> G'=bar(G)

a(G') = n - μ_G(1)

G -> G'=T(G)

(G,v) -> G'=G-v

a(G') >= a(G) - 1

(G,v) -> G'= (G-v and then +e), smoothing of v

(G,v,k,l), k >= l >= 1, -> G' = v에서 길이가 k, l인 path를 attaching, G'' = v에서 길이가 k+1, l-1인 path를 attaching

a(G') >= a(G'') (Guo 2010)

(G,v) -> G' = adding some edges among pendent vertices at v

if a(G) != 1, then a(G) = a(G') (Shao, Guo and Shan 2008)

(G,U,V) -> VD(G) = (G[U], G[V])

a(VD(G)) <= min(a(G[U]) + |V|, G[V] + |U|)

(G,v,u1,u2,...,uk), each ui not adjacent to v -> G' = G+H, where V(H)=(v,u1,...,vk), v~ui for any i

if G' not K_n, then a(G') - a(G) <= k - eps where eps is the smallest positive root of

"d(v) * eps * (k - eps) - (1 - eps)^2 * (k - 1 - eps)^2" (Kirkland, Oliveira and Justel 2011)

(G,e) -> G'=subdivision of e

a(G') <= a(G)

(G,e) -> G'=contraction of e

(G,e) -> G'=G-e

a(G') <= a(G)

(G,e) -> G'=G+e,

a(G') >= a(G)

(G,v,e) -> G'=G+pe

if G, G':both trees, then a(G') <= a(G)

G1, G2 -> G1+G2

a(G1+G2) = 0

G1, G2 -> G1VG2

a(G1vG2) = min(a(G1)+n2, a(G2)+n1)

G1, G2 -> G1xG2

a(G1xG2) = min(a(G1), a(G2))

G1, G2 -> EDP(G1,G2)

G1, G2 -> DS(G1,G2)

a(DG(G1,G2)) >= a(G1) + a(G2)

(G1,u), (G2,v) -> G = identifying u and v

a(G) <= min(a(G1),a(G2))

(G1,u), (G2,v) -> G' = (G1+G2) + (uv), G'' = G' and then identifying u and v(say u) and then +(uw),

a(G') <= a(G'') (Guo 2010)

(G,u,v) with some nbds of v(Specifically, {v1,v2,...,vs}:subset of N(v) - N(u) and any vi is different from u), G' = G - vv1-vv2-...-vvs + uv1 + uv2 + ... + uvs

if y(u)=y(v), then a(G') <= a(G)(Lama 2016)

-----------------------------------------------------------------------------------------------------------------------

*Extremal Problems

(Among tree, n, D(G))a(T(a,b,c)) is the minimum where a = ]](n-c)/2[[, b = [[(n-c)/2]], c = D(G) - 1(Fallat and kirkland 1998)

------------------------------------------------------------------------------------------------------------------------

*Problems

(Among Tree)one edge subdivision always make a(G) decreasing.

------------------------------------------------------------------------------------------------------------------------

읽었는 논문

읽을 논문

1. linux live usb creator를 이용하여 설치하고자하는 리눅스를 usb에 설치

2. 1번에서 설치한 usb로 부팅한 다음에 ubuntu설치(www.linuxbsdos.com참고)

-반드시 영어로 설치

-외장하드를 3개의 partition필요, 

-a:primary patition이고 use as:Ext4 journaling file system, mount point:/(root), size는 최소(6,7기가 이상이면 상관없음)

-b:primary partition이고 use as:swap area, size는 2기가정도

-c:free space

-device for boot loader installation:외장하드로 선택 필요

(반드시 설치하고자하는 기기종류와 운영체제 설치법을 구글링하여 얻은 자료 토대로 설치할 것)

3. 이후 우분투 설치후 SAGE설치법

-http://www.sagemath.org/documentation/html/en/installation/index.html

-"Pre-built Binary Install  Linux and OS X"선택

-우분투 버전에 맞는 sage를 다운받은후 (mirror사이트에서) 다운 받은 폴더에서

tar zxvf sage-x.y.z-x86_64-Linux.tgz

해서 압축을 푼 다음에

ln -s /path/to/sage-x.y.z-x86_64-Linux/sage /usr/local/bin/sage

-압축 푼 폴더 안에서 터미널에서 make를 입력하면 make가 안될 수 있다. 오류를 읽어보면 dpkg-dev이란게 없다고 하는데 터미널에서 sudo apt-get install dpkg-dev

-압축 푼 폴더 안에서 터미널에서 ./sage -sh한 다음에 exit하고 그다음에 ./sage -i dot2tex

-sudo apt-get install texlive해서 texlive도 설치

-우분투 소프트웨어센터에서 dot2tex검색해서 dot2tex2.8.7버전도 설치

-우분투 소프트웨어센터에서 texlive도 설치

-압축 푼 폴더 안에서 터미널에서 make입력, 시간이 오래 걸림

4. sage내에서 tableaux그리는게 가능, view(B)명령어 됨

L:lie algebra

1. L:solvable이면 for any x in [LL], ad_L x : nilpotent임을 보여라.

cf)L:nilpotent이면 for any x in L, ad_L x : nilpotent

2. x:semisimple in End(V)이면 adx:semisimple임을 보여라.

Title:Crystals For Dummies

Author:Mark Shimozono

*Summary

1. Tensor Product가 commutative(up to crystal graph isomorphism)한 것은 not natural(Representation Theory를 이용하여야 함)

2. Crystal Graph의 unary operation, dual(v), Dynkin Autormophism(*), # operation

-v은 arrow방향이 바뀐다는 게 중요

-*은 color가 바뀐다는 게 중요

-#은 v취한 다음에 *취한 것, 따라서 arrow방향과 color가 모두 바뀜 

3. B(dominant wt):connected, 그리고 그 때의 highest weight vector

4. B:connected이면 B isomorphic B(lambda) for some lambda(dominant)

5. Decomposition 

-general Crystal Graphs

-B(1)^k일 때

-Yamanouchi word가 highest wt vector이고 dominant wt를 wt로갖는 Yamanouchi word를 세는 일=Standard Tableaux개수 세는 일

-Recording으로 (P(b),Q(b)) 구할 수 있음

-B(r)xB(lambda)일 때

-LR coefficient 도입

-set of seq of weakly increasing words를 행렬로 나타낸 뒤 transpose의미로 bijection얻는 것(wt, shape)<->(shape,wt)

-B^beta일 때

-결국 horizontal strip을 반복적으로 넣는 행위는 semistandard tableaux를 세는 일

-Recording으로 (P(b),Q(b)) 구할 수 있음

*Question

1. P4, 2 paragraphs, Weyl Group관련

2. P4, simple root, simple coroot관련

3. P4, Rmk 2.4 gl_n-weight lattice, sl_n-weight lattice

4. P5, Crank와 automorphisms of conjugation이 commute하는 것

5. P9, Contragredient dual of a module이란

6. P9, Dynkin Diagram, Dynkin automorphism이란

dual부터 복습

즉 bumping은 그 row에서 판단 후 아래로 보내고

inverse는 위로 보낸 다음 판단

-(def) (bumping) route of a row-bumping이란?

-(def) the new box of a row-bumping이란?

-(def) strictly left, weakly left, of two routes란?(routes의 대소비교 가능)

-(Lem) Row Bumping Lemma

-한 tableau에 bumping을 두번할 때(using x1, x2) 얻어진 two routes의 대소와 two new boxes의 위치관련정보(x1,x2의 대소로써)

-(Prop)

-한 tableau에 bumping을 여러번할 때 skew diagram의 new boxes위치 관련(단, weakly inc한 숫자를 or strictly dex한 숫자를)

-역으로 한 tableau와 포함된 young diagram 그리고 그것의 skew diagram의 new boxes위치를 통해 그 young diagram에 row-bumping해서 tableau를 얻었음을 알 수 있다.

-(def) a product tableau란?

-(Claim)(not proven) the product operation makes the set of tableaux into an associative monoid(empty tableau가 unit)

-(def) an inside corner of a skew diagram

-(def) an outside corner of a skew diagram

-(def) a sliding of a skew tableau이란

-(Rmk) a sliding of a skew tableau또한 skew tableau된다.(각 step마다 tableau인게 유지됨)

-(Rmk) sliding 또한 reverse를 갖는다

-(def) a reverse slide란?(result skew tableau와 removed box의 위치를 안다면)

-(def) a rectification of a skew tableau이란?

-(def) the jeu de taquin of a skew tableau이란?

-(Claim)(not proven) Starting with a given skew tableau, all choices of inner corners lead to the same rectified tableau.

-(note) 즉 inside corner를 택하는 방식이 어떻든 rectification은 unique

-(def) a product tableau using sliding, rectification

-(Claim)(not proven) The product using sliding agrees with the first definition

(Chapt2 Words; the plactic monoid)

-(def) the word of a skew tableau란? the word of a tableau란?

-(Rmk) {tableau} bijective {the word of some tableau}, 하지만 word of a skew tableau는 skew tableau를 determine하지 못한다.

-(Rmk) 그냥 word라 하면 skew tableau에서 온건지 tableau에서 온건지 모른다. 그리고 그게 중요하진 않음

-(Rmk) row-bumping of a tableau by x을 word language로 하면 어떻게 되는가?(row로 piece한 다음에)

-(Rmk) Knuth는 row-bumping of a tableau by x을 computer programming language로 표현(한 row안에서 착착착)

-(def) an elementary Knuth transformation on a word란?

-(def) two words가 Knuth equivalent란?

-(Prop) row-bumping 한 다음에 word 구한 것 is Knuth equivalent to word구한것에 bumping할 x를 juxtaposition

-(note) 즉 bumping한 것의 word구하는 것은 먼저 word구한 다음에 bumping할 x를 juxtaposition(오른쪽으로)한 다음에 row단위로 Knuth transformation하면 얻을 수 있다.

-(Cor) W(TU) is Knuth equivalent to W(T)W(U)

-(Prop) If one skew tableau can be obtained from another by a sequence of slides, then their words are Knuth equivalent.

-(note) 즉 sliding해봤자 Knuth equivalent classes는 바뀌지 않는다.

-(Thm)(not proven) Every word is Knuth equivalent to the word of a unique tableau.

-(Rmk) 어떤 word가 있을 때 constructing a tableau whose word is Knuth equivalent to given word이 가능하다, 주어진 word의 letter순으로 bumping하면됨

-(def) 위의 과정을 canonical procedure이라 한다.

-(Cor) the rectification of a skew tableau is the unique tableau, 그리고 skew tableau의 word와 unique tableau의 word는 Knuth equivalent

-(Cor) skew tableau가 2개 있을 때, rectification이 same iff 각 skew tableau의 word가 Knuth equivalent

-(note) 따라서 product tableau를 unique tableau whose word is Knuth equivalent to word1word2로도 정의가 가능하다. 즉 각각의 tableau의 word를 구한 다음 병렬로 나열한 다음에 Knuth transformation을 계속 써서 tableau로 만들고 그 때 얻은 tableau를 product tableau라 하자는 것, 그것의 유일성은 Thm이 보장해주는 것

-(Cor) The three constructions of the product of two tableaux agrees

-(def) the plactic monoid란?

-(def) the tableau ring of [m]이란?([m]={1,2,3,...,m})

-(def) the Schur polynomial이란?(using the tableau ring of [m], lambda as shape)

-(Rmk) Pieri formulas란?

-[m]:fixed 상황에서 Schur polynomial과 (complete or elementary) symmetric polynomial과의 곱연산 공식을 제공한다.(shape끼리의 연산, 다른 말론 partition끼리 연산)

(이 공식은, (tableau1+tableau2+...)(tableau1'+tableau2'+...)에다가 monomial을 취하고 monomial이 multiplicative인 것을 이용한 셈)

(한 tableau가 monomial을 1개만 갖지만, 역은 성립하지 않는다, monomial은 tableau를 여러개 결정시킴)

-(def) a tableau has content (mu1,mu2,...mul)이란?

-(Rmk) content는 tableau의 monomial로써 생각이 가능(bijective from {content} to {monomial})

-(Rmk) monomial->tableau는 1개로 결정안되지만, 이 때의 모든 tableau는 content가 같다.

-(Rmk) content에다가 shape을 추가시켜도 tableau가 여러개 있을 수 있다.

-(def) a Kostka number of (shape, content)란?

-(Rmk) 두 tableau가 content가 같으면 대응되는 monomial이 같은 것, 역으로 monomial이 같은 tableau면 content가 같은 것

-(Rmk) Kostka number를 polynomial입장에서는 특정 monomial(determined by content)이 특정 shape로 얻어지는 개수, 즉 coefficient from the particular shape

-(Rmk) is the same the number of sequences of partitions s.t. ... 가능

-(Rmk) complete symmetric polynomial의 연속 곱에 대한 정보 줌 

-(Rmk) 

1. (Computing the mean time until a given pattern occurs)

동전 던지기를 반복적으로 시행을 할 때, 다음의 패턴이 처음으로 나오면 시행을 그만 두기로 하자.

"앞뒤앞뒤앞뒤앞"

이때 평균적으로 몇번을 시행해야 하는가?

만약 패턴이 다음으로 바뀐다면, 평균 시행횟수는 어떻게 달라지는가?

"앞앞뒤뒤앞앞뒤"

(link1)(link2)

2. (Secretary Problem)

인사담당자가 N명의 비서 지원자들 중 1명을 고용하기로 한다. 이 때 다음의 가정을 따른다.

(1) 각 지원자들을 한명씩 검토한다.

(2) 검토 후 고용하지 않는다면, 이후에도 절대 고용하지 않는다.(즉, 지원자는 다른 회사로 고용된다고 하자.)

(3) 검토 후 이때까지 만난 비서들의 능력을 대소 비교할 수 있다. 하지만 검토하지 않은 비서의 능력은 검토하기까지는 모른다.

이때, 인사담당자가 지원자들을 검토하는 중, 최고의 능력을 가진 비서를 뽑기 위해선 몇 명쯤 까지 검토하여야 하는가?

(link1)(link2)(link3)

3. (Unexpected dependent variables)

J={w1,w2}

C4=Power set of J

P({w1})=1/2, P({w2})=1/2

(J,C4,P):Probability Measure Space

이 때, X(w1)=0, X(w2)=1로 정의된 rdv X와 Y(w1)=1, Y(w2)=0으로 정의된 rdv Y는 independent이다. 거짓

따라서, independent에 있어서, New variable이 older one과 관계없이 정의된 것 같아도, 잘 따져줘야 한다.

4. (Markov Decision Process with finite horizon, MDP with finite horizon)

reward depending (state, action)이 deterministic인 MDP with finite horizon일 때, reward를 최대로할 sequence of actions를 찾아라.

(link)

5. 

DF(x)<1 for all x in R인 rdv를 독립시행을 계속할 때, 갱신되는 최댓값은 결국 +inf가 되는가? 참

(link)

6. 

DF인 F가 conti일 때, int over R DF(x)F(dx)=1/2

(link)

7. 

X_1, X_2가 rdv이고 iid with common continuous DF인 F, P(X_1<=X_2)=1/2임을 보여라.

(link)

8. (P(limsup E_n)을 구하는 데 있어서 Borel Zero-one Law를 쓰진 못하지만...)

infinite independent fair coin tossing experiment를 생각하자. H_n:={n-th coin tossing results in a head}

B_n := f-intersection from i=1 to i=[log_2 (n)] H_(n+i) where [x]:=floor function

이 때 P(limsup B_n)=1임을 보여라.

9. (Classical Coupon Collecting)

n개의 서로 다른 쿠폰이 uniformly distributed하게 얻어진다고 하자. 

즉, {X_k, k>=1}:iid and uniformly distributed on {1,2,3,...,n}

(a) 

t번의 시행시 모든 종류의 쿠폰들이 적어도 1개씩은 뽑힐 확률은?

(link)

(b)

이 때, n개의 쿠폰을 모두 모으기 위한 최소시행 T_n은 다음을 만족함을 보여라. 

[T_n/{n*ln(n)}] cv in M to 1

(즉, 서로 다른 10,000개의 쿠폰을 모두 모으기 위한 최소시행횟수는 거진 10,000*(ln(10,000)), 약 92,000이다.)

(link)

10. (Pure Birth Process)

{X_k, k>=1}:rdv, ind, nnn, 각각이 l_n>=0을 parameter로 하는 exp-distri라 하자.

X_k는 1마리가 탄생할 때까지 걸리는 시간을 뜻한다.

S_n := sum from k=1 to k=n X_k (n마리가 탄생할 때까지 걸리는 시간)

애초에 1마리가 있다고 가정하자. (탄생한게 아닌, 이미 존재한 객체 1마리)

Y_t := the population size process of the pure birth process

이때, ProbM(explosion)을 구하여라.

(link)

11.(Occupation Times)

{rdv_t,0<=t<=1}, continuous time stochastic process가 어떠한 time interval에서 어떠한 실수값을 몇번 찍을 것인가?

(link)

12. (HGD의 application)

공장주가 25개의 기계를 샀을 때, 10개의 제품을 test했더니 not defective일 때, 총 25개중 6개가 defective일 확률은?

(link)

13. (PD의 application)

전화상담사가 평균적으로 3분마다 5개의 calls를 해결한다. 그리고 1분동안 전화오는 횟수는 PD(lambda)를 따른다.

(a)

다음 1분동안 call이 한통도 없을 확률은?

(link)

(b)

다음 1분동안 at least two calls가 있을 확률은?

(link)

14. (비둘기집의 원리 예)

수열 7,77,777,7777,77777,...중 2003의 배수가 등장함을 증명하여라.

(link)

1. 

p:odd prm

Show that p ≡ 1 (mod 4) iff x^2 ≡ (-1) (mod p) has an integer solution

(link)

2. 

G:finite group

H:subgroup of G

G=union of xHx^(-1) over all x in G

이면 G=H이다.

(link)

3. 

G:group

H:subgroup of G s.t. [G:H]<inf

이면 te N s.t. N:proper normal in G, [G:N]<inf

(link) 

4.

Prove that there is no simple group of order 525=3*5^2*7

(link)

5. 

|G|=21, non-cyclic group

Find the number of sylow 3-subgroups of G

(link)

6.

|G|=45=3^2*5, group

Prove that there is an element g in G s.t. |g|=15=3*5

(link)

7.

Find the number of sylow 7-subgroups of S_7

(link)

8. 

(TS,top1), (TS,top2), top1<top2일 때

(1) top1이 T2이면 top2도 T2인가?

(2) top1이 T3이면 top2도 T3인가?

(3) top1이 T4이면 top2도 T4인가?

(link)

9.

|G|=2^3 3^4 5^2 7인 finite abelian group일 때, elementary divisor로 classification, invariant factor로 classification(link)

1.(About symmetric)

-용어정의

-R이 symmetric란, for any a,b in X, R(a,b)이면 R(b,a)이다.

-R이 asymetric란, for any a,b in X, R(a,b)이면 not R(b,a)이다.

-R이 antisymmetric란, for any a,b in X, R(a,b) and R(b,a)이면 a=b이다.

(혹은 for any a,b in X, R(a,b)이고 a != b이면 not R(b,a)이다.)

symmetric의 부정은 asymmetric인게 아님.

asymmetric이면 irreflexive

irreflexive이고 antisymmetric의 필요충분은 asymmetric

(antisymmetric은 symmetric의 부정과도 비슷하지만, R(a,a)가 있을 수도 있을 때 이용)

2. (About reflexive)

-용어정의

-R이 irreflexive란, for any a in X, not R(a,a)이다.

-R이 reflexive란, for any a in X, R(a,a)이다.

irreflexive는 strict에서 사용(따라서 strict는 irreflexive나 asymmetric을 이용)

reflexive는 non-strict에서 사용(따라서 symmetric하지 않음이 필요하다면 antisymmetric사용)

irreflexive는 reflexive의 부정은 아님

3. (About totality)

-용어정의

-R이 total이란, for any a,b in X, R(a,b) or R(b,a)(둘다 성립해도 괜찮)

-R이 trichotomous란, for any a,b in X, 다음 3가지중 단 1개만 성립, R(a,b), a=b, R(b,a)

total이기 위해선 일단 reflexive여야 함(따라서 non-strict에서 totality가 필요할 때 total이용)

trichotomous는 irreflexive하면서 total한 느낌 살릴 때 이용(따라서 strict에서 totality가 필요할 때 trichotomous이용)

4. 

-용어정의

-R이 transitive란, R(a,b) and R(b,c)이면 R(a,c)이다.

transitive함이 ordering relation에서 기본적으로 필요

5. 

Order Relation에서는 고려해야할 것

(1) transitive반드시 필요, 

(2) reflexive, irreflexive 결정하면->symmetric(symmetric, antisymmetric, asymmetric)도 결정됨

(strict인 경우 irreflexive여야하고 그땐 (3) symmetric에서 결정안해도됨)

(non-strict인 경우 reflexive여야하고 그땐 (3) symmetric에서 antisymmetric여야함) 

(3) totality(total, trichotomous)결정

(strict인 경우 trichotomous결정)

(non-strict인 경우 total결정)

(이후 중복조건 제거, 예를 들면 total이면 reflexive됨)

*********이제부턴 다음이 유도가 쉬워짐**************

not total ordering relation

-non-strict partial ordering relation:transitive, reflexive, antisymmetric(모든 원소는 적어도 자기자신과는 relation되어야)

-strict partial ordering relation:transitive, irreflexive(모든 원소가 relation이지 않아도 됨)

total ordering relation

-non-strict total ordering relation:transitive, (reflexive), antisymmetric, total

-strict total ordering relation:transitive, irreflexive, trichotomous