Summations & Cardinality & Matrices

Summations

Summations

• Sum of the terms
  
  • Notation
    
    • Represent
      
    • variable j: index of summation
    • m: lower limit
    • n: upper limit

  • for a set S
    

    • If S = {2, 5, 7, 10}
    • a2 + a5 + a7+ a10 ≠ 2 + 5 + 7 +10
    • S: a set of indices

Geometric Series

• Sums of terms of geometric progressions(등비수열)
  

---

Cardinality

Cardinality of Sets

• Cardinality
  • |A| = |B| ↔︎ one-to-one correspondence(bijection)
• Countable
  • finite set
  • infinite set (Countably infinite)
    • 양의 정수(Z+) 집합과 같은 cardinality를 갖는 무한 집합
      • |A| = |Z+| = ℵ0
    • ↔︎ 무한 집합 중에서 자신의 원소들을 양의 정수로 index를 달면서 순서대로 나열할 수 있는 경우
    • ℵ0 (aleph): countably infinite’s cardinality
    • |S| = ℵ0 : aleph null

Showing that a Set is Countable

• 집합이 countable임을 증명
  • f is a one-to-one correspondence(bijection) from N to a set S
    • show that it is one-to-one
      • f(n) = f(m) -> n = m
    • show that it is onto
      • f(x) = y

Countable Sets and Uncountable sets

• Countable Sets
  • set of finite strings = countably infinite
  • set of all Java programs
  • the positive rational numbers(유리수)
• Uncountable sets
  • the real numbers(실수) (R)

---

MATRICES

Illustration of Matrix Multiplication

Identity Matrix and Powers of Matrices

• Identity Matrix (항등 행렬) In
  • 주대각선의 원소가 모두 1이며 나머지 원소는 모두 0인 정사각 행렬
  • AIn = ImA = A (결과 = A matrix로 같다)
• Powers of square matrices
  • A^0 = In
  • A^r = AAA…A (r times)

Transposes of Matrices

• : m x n matrix
• Transpose of A
  • : n x m matrix

• 

  • for i = 1, 2, … , n and j = 1, 2, …, m

• square matrix A
  → symmetric
• 
  • for i and j with 1≤i≤n and 1≤j≤n
    

Zero-One Matrices

• zero-one matrix
  • 모든 항목이 0 or 1

Joins and Meets of Zero-One Matrices

• Joins and Meets
  

  • The join of A and B
    

  • The meet of A and B
    

Boolean Product of Zero-One Matrices

• A = [aij] : m x k zero-one matrix
• B = [bij] : k x n zero-one matrix
• The Boolean product of A and B
  • A ⊙ B : m x n zero-one matrix

• Ex)