Discrete math-এ matrix — 0-1 matrix আর Boolean product

১ · Matrix — দ্রুত পুনরালোচনা, discrete চোখে

বাজারঘরের তিনটি গুদাম (G1, G2, G3) আর চারটি জেলা (ঢাকা, চট্টগ্রাম, খুলনা, রাজশাহী)। কোন গুদাম কোন জেলায় সরাসরি পার্সেল পাঠায়, তা একটি ছকে লিখলে সারি হয় গুদাম, কলাম হয় জেলা, আর প্রতিটি ঘরে “হ্যাঁ” হলে 1, “না” হলে 0. এই ছকটিই একটি matrix. Discrete math-এ matrix সাধারণত এভাবেই আসে: দুটি সসীম সেটের মধ্যে কোন জোড়া সম্পর্কিত, তার হিসাব। পর্ব ১৪ “সেট — সংজ্ঞা, subset, power set আর Cartesian product”-এ দেখেছেন, A × B-এর যেকোনো subset একটি relation; সসীম সেটে সেই relation-কে লেখার সবচেয়ে সরাসরি উপায় এই 0-1 ছক।

বাস্তব সংখ্যার matrix, তার জ্যামিতি আর linear algebra এই কোর্সে আবার শেখানো হবে না: তার জন্য Machine Learning কোর্সের পর্ব ০৬ আর পর্ব ০৭, আর NumPy-তে হাতে-কলমে AI Foundations কোর্সের পর্ব ১৭ দেখুন। এখানে আমরা শুধু সংজ্ঞাগুলো এক জায়গায় রাখব, তারপর এমন জিনিসে যাব যা ওই কোর্সগুলোতে নেই: 0-1 matrix, Boolean product আর গুণের খরচ গোনা।

এখানে ∑ হলো summation চিহ্ন: t = 1 থেকে k পর্যন্ত প্রতিটি পদের যোগফল। পর্ব ১৭ “Sequence আর summation — closed form আর বিখ্যাত যোগফল”-এ এর নিয়মগুলো (index বদল, double sum) আসছে; এখানে আমাদের শুধু এই একটি সংজ্ঞা লাগবে।

একটি ছোট উদাহরণ হাতে কষে দেখা যাক। M = [[1, 2, 0], [0, 1, 3]] (2 × 3) আর N = [[1, 0], [2, 1], [0, 4]] (3 × 2). MN-এর (1, 1) ঘর = 1·1 + 2·2 + 0·0 = 5; (1, 2) = 1·0 + 2·1 + 0·4 = 2; (2, 1) = 0·1 + 1·2 + 3·0 = 2; (2, 2) = 0·0 + 1·1 + 3·4 = 13. তাই MN = [[5, 2], [2, 13]], একটি 2 × 2 matrix. অথচ NM একটি 3 × 3 matrix: একই দুটি matrix, উল্টো ক্রমে গুণ করলে আকারই আলাদা। (এখানে [[…], […]] মানে সারিগুলোর তালিকা, Python-এর মতো করে লেখা।)

২ · গুণের নিয়ম — non-commutativity, identity, ঘাত আর transpose

সংখ্যার গুণে ab = ba. Matrix-এর গুণে এই নিয়ম ভাঙে, আর এটিই সবচেয়ে বেশি ভুলের উৎস। আকার না মিললে তো BA সংজ্ঞায়িতই না-ও হতে পারে; কিন্তু বর্গ matrix-এও সাধারণত AB ≠ BA. একটি counterexample-ই যথেষ্ট (পর্ব ০৯-এর counterexample দিয়ে খণ্ডন):

P = [[1, 1], [0, 1]], Q = [[1, 0], [1, 1]] ⇒ PQ = [[2, 1], [1, 1]], কিন্তু QP = [[1, 1], [1, 2]]

কারণটা পর্ব ১৬-এ দেখা composition-এর মতোই। Matrix গুণ আসলে দুটি রূপান্তর পরপর প্রয়োগ, আর composition সাধারণত বিনিময়যোগ্য নয়: আগে মোজা পরে জুতা, আর আগে জুতা পরে মোজা, এক জিনিস নয়।

প্রমাণ:

1. (ক) দুই পাশই m × p. সংজ্ঞা দুবার লাগিয়ে ((AB)C)_ij = ∑_s (AB)_isc_sj = ∑_s ∑_t a_itb_tsc_sj. — গুণের সংজ্ঞা, বণ্টন নিয়ম
2. একইভাবে (A(BC))_ij = ∑_t a_it(BC)_tj = ∑_t ∑_s a_itb_tsc_sj. সসীম double sum-এ যোগের ক্রম বদলালে ফল বদলায় না, তাই দুটি সমান। — যোগের বিনিময় আর সংযোগ নিয়ম
3. (খ) (AB)^T আর B^TA^T দুটিই n × m. ((AB)^T)_ij = (AB)_ji = ∑_t a_jtb_ti. — transpose আর গুণের সংজ্ঞা
4. (B^TA^T)_ij = ∑_t (B^T)_it(A^T)_tj = ∑_t b_tia_jt. সংখ্যার গুণ বিনিময়যোগ্য, তাই প্রতিটি পদ ধাপ ৩-এর পদের সমান। — সংখ্যার commutativity
5. (গ) (খ) থেকে (AA^T)^T = (A^T)^TA^T = AA^T, কারণ দুবার transpose নিলে আগের matrix ফেরে। ∎

লক্ষ করুন, (খ)-এর প্রমাণে সংখ্যার গুণের commutativity লেগেছে, matrix-এর নয়। আর ফলে ক্রম উল্টে গেছে, ঠিক পর্ব ১৬-এর (g∘f)⁻¹ = f⁻¹∘g⁻¹-এর মতো। (A + B)² খুললে পাওয়া যায় A² + AB + BA + B²; AB = BA না হলে একে A² + 2AB + B² লেখা যায় না। নিচের ব্লক এই সব দাবি ছোট উদাহরণে পরীক্ষা করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

def mul(A, B):                      # ordinary product: row i of A times column j of B
    assert len(A[0]) == len(B), "inner sizes differ"
    return [[sum(A[i][t] * B[t][j] for t in range(len(B))) for j in range(len(B[0]))]
            for i in range(len(A))]

def T(A):                           # transpose: rows become columns
    return [list(col) for col in zip(*A)]

def size(A):
    return f"{len(A)}x{len(A[0])}"

I = [[1, 0], [0, 1]]
P = [[1, 1], [0, 1]]
Q = [[1, 0], [1, 1]]
print("PQ =", mul(P, Q), "  QP =", mul(Q, P))
print("IP == PI == P:", mul(I, P) == mul(P, I) == P)
print("P^2 =", mul(P, P), "  P^3 =", mul(mul(P, P), P))

M = [[1, 2, 0], [0, 1, 3]]          # 2x3
N = [[1, 0], [2, 1], [0, 4]]        # 3x2
print("MN is", size(mul(M, N)), "  NM is", size(mul(N, M)))
print("(MN)^T == N^T M^T:", T(mul(M, N)) == mul(T(N), T(M)))
print("M^T N^T is", size(mul(T(M), T(N))), "so it cannot equal (MN)^T")
S = mul(M, T(M))
print("M M^T =", S, "  symmetric:", S == T(S))

S2 = [[P[i][j] + Q[i][j] for j in range(2)] for i in range(2)]
lhs = mul(S2, S2)
rhs = [[mul(P, P)[i][j] + 2 * mul(P, Q)[i][j] + mul(Q, Q)[i][j] for j in range(2)]
       for i in range(2)]
print("(P+Q)^2 =", lhs, "  P^2+2PQ+Q^2 =", rhs)

PQ = [[2, 1], [1, 1]]   QP = [[1, 1], [1, 2]]
IP == PI == P: True
P^2 = [[1, 2], [0, 1]]   P^3 = [[1, 3], [0, 1]]
MN is 2x2   NM is 3x3
(MN)^T == N^T M^T: True
M^T N^T is 3x3 so it cannot equal (MN)^T
M M^T = [[5, 2], [2, 10]]   symmetric: True
(P+Q)^2 = [[5, 4], [4, 5]]   P^2+2PQ+Q^2 = [[6, 4], [4, 4]]

৩ · 0-1 matrix — join, meet আর Boolean product

এবার এমন matrix, যার প্রতিটি ঘর 0 বা 1: “সম্পর্ক আছে” বা “নেই”। এদের সঙ্গে সবচেয়ে স্বাভাবিক অপারেশন যোগ-গুণ নয়, বরং পর্ব ০২-এর ∨ (অথবা) আর ∧ (এবং), যেখানে 1 মানে সত্য আর 0 মানে মিথ্যা। কম্পিউটার আর্কিটেকচার কোর্সের পর্ব ০৭-এ এই অপারেশনগুলো logic gate হিসেবে এসেছে; এখানে তারা matrix-এর ঘরে বসবে।

সংজ্ঞাটি সাধারণ গুণের হুবহু ছক, শুধু “গুণ” হয়েছে ∧ আর “যোগ” হয়েছে ∨. কথায়: (A ⊙ B)_ij = 1 ঠিক তখন, যখন অন্তত একটি t আছে যাতে a_it = 1 এবং b_tj = 1. বাজারঘরের ভাষায়: W যদি বলে কোন গুদাম কোন hub-এ মাল পাঠায়, আর H বলে কোন hub কোন জেলায় পাঠায়, তবে W ⊙ H বলে কোন গুদাম অন্তত একটি hub হয়ে কোন জেলায় পৌঁছাতে পারে। মাঝের t হলো সেই hub. Join আর meet ঘরে ঘরে কাজ করে, পর্ব ১৫ “সেটের অপারেশন — union, intersection, Venn diagram আর identity”-এর union আর intersection-এর মতো, আর আসলে ঠিক তাই: matrix দুটি দুটি relation হলে join তাদের union, meet তাদের intersection.

1W: গুদাম × hub (H1 H2 H3)2G1: 1 0 13G2: 0 1 04H: hub × জেলা (KHL SYL)5H1: 0 1   H2: 1 0   H3: 1 16কলাম KHL = 0 1 17কলাম SYL = 1 0 1

শেষ ধাপের তুলনাটি একটি সাধারণ সত্য: সাধারণ গুণফলের যে ঘর 0-এর বেশি, Boolean product-এ ঠিক সেই ঘর 1. এটি প্রমাণ করে নেওয়া যাক, কারণ এর ওপর ভর করেই ⊙-এর বাকি নিয়মগুলো সহজে আসে।

প্রমাণ:

1. (AB)_ij = ∑_t a_itb_tj. প্রতিটি পদ 0·0, 0·1, 1·0 বা 1·1, অর্থাৎ 0 বা 1; আর a_itb_tj = 1 ⇔ a_it = 1 এবং b_tj = 1 ⇔ a_it ∧ b_tj = 1. — 0-1 সংখ্যার গুণ আর ∧-এর truth table একই
2. অঋণাত্মক সংখ্যার যোগফল 0-এর বেশি ⇔ অন্তত একটি পদ 0-এর বেশি। — সব পদ ≥ 0
3. তাই (AB)_ij > 0 ⇔ কোনো t-তে a_it ∧ b_tj = 1 ⇔ (A ⊙ B)_ij = 1. ∎ — ∨-এর সংজ্ঞা: অন্তত একটি সত্য

প্রমাণ: অঋণাত্মক পূর্ণসংখ্যার যেকোনো matrix X-এর জন্য ⟦X⟧ লিখি সেই 0-1 matrix, যার ঘর 1 ঠিক যেখানে X-এর ঘর ধনাত্মক। উপপাদ্য ৩.২ বলে A ⊙ B = ⟦AB⟧.

1. দাবি: X, Y অঋণাত্মক হলে ⟦⟦X⟧Y⟧ = ⟦XY⟧. কারণ (XY)_ij = ∑_t x_ity_tj > 0 ⇔ কোনো t-তে x_it > 0 আর y_tj > 0 ⇔ কোনো t-তে ⟦X⟧_it = 1 আর y_tj > 0 ⇔ (⟦X⟧Y)_ij > 0. একইভাবে ⟦X⟦Y⟧⟧ = ⟦XY⟧. — উপপাদ্য ৩.২-এর যুক্তি
2. (A ⊙ B) ⊙ C = ⟦⟦AB⟧C⟧ = ⟦(AB)C⟧, আর A ⊙ (B ⊙ C) = ⟦A⟦BC⟧⟧ = ⟦A(BC)⟧. — ধাপ ১
3. উপপাদ্য ২.২(ক) অনুযায়ী (AB)C = A(BC), তাই দুই পাশ সমান। — সাধারণ গুণের associativity
4. অসমতার জন্য একটি counterexample: X = [[1, 0, 1], [0, 1, 1], [1, 0, 0]], Y = [[0, 1, 0], [1, 0, 1], [0, 1, 1]] নিলে X ⊙ Y-এর (2, 2) ঘর 1, কিন্তু Y ⊙ X-এর (2, 2) ঘর 0 (নিচের ব্লকে পুরো দুটি matrix). ∎

এই উপপাদ্যগুলোর একটি সুন্দর ব্যাখ্যা relation-এর ভাষায়। গুদাম থেকে hub-এর relation R-এর matrix যদি M_R হয়, আর hub থেকে জেলার relation S-এর matrix M_S, তবে “গুদাম থেকে কোনো hub হয়ে জেলা” relation-টি হলো R আর S-এর composition, আর তার matrix ঠিক M_R ⊙ M_S. ফাংশনের composition-এর মতোই এখানে ক্রম গুরুত্বপূর্ণ, আর associativity মানে তিনটি ধাপ জুড়তে কোন দুটি আগে জুড়লেন তাতে কিছু যায় আসে না। Relation-এর এই হিসাব প্রমাণসহ আসবে পর্ব ৫২ “Relation আর তার ধর্ম — reflexive, symmetric, transitive”-এ।

নিচের ব্লক ⊙ শূন্য থেকে লেখে (শুধু any আর and দিয়ে), stepper-এর উদাহরণ আর উপপাদ্য ৩.৩-এর counterexample ছাপে, তারপর নির্দিষ্ট seed-এ ২,০০০টি এলোমেলো আকার ও মানের matrix-এ উপপাদ্য ৩.২ আর ৩.৩ পরীক্ষা করে। মনে রাখবেন, এলোমেলো পরীক্ষা আস্থা দেয়, প্রমাণ দেয় উপপাদ্য।

import random
random.seed(19)

def bool_product(A, B):    # (A ⊙ B)[i][j] = OR over t of (A[i][t] AND B[t][j])
    assert len(A[0]) == len(B), "inner sizes differ"
    return [[int(any(A[i][t] and B[t][j] for t in range(len(B))))
             for j in range(len(B[0]))] for i in range(len(A))]

def int_product(A, B):
    return [[sum(A[i][t] * B[t][j] for t in range(len(B)))
             for j in range(len(B[0]))] for i in range(len(A))]

def join(A, B): return [[a | b for a, b in zip(r, s)] for r, s in zip(A, B)]
def meet(A, B): return [[a & b for a, b in zip(r, s)] for r, s in zip(A, B)]

W = [[1, 0, 1], [0, 1, 0]]          # warehouse x hub
H = [[0, 1], [1, 0], [1, 1]]        # hub x district
print("W ⊙ H =", bool_product(W, H), "   W H =", int_product(W, H))
X = [[1, 0, 1], [0, 1, 1], [1, 0, 0]]
Y = [[0, 1, 0], [1, 0, 1], [0, 1, 1]]
print("X ∨ Y =", join(X, Y), "   X ∧ Y =", meet(X, Y))
print("X ⊙ Y =", bool_product(X, Y), "   Y ⊙ X =", bool_product(Y, X))

def rand01(r, c):
    return [[random.randint(0, 1) for _ in range(c)] for _ in range(r)]

same = assoc = 0
for _ in range(2000):
    n, k, m, p = (random.randint(1, 5) for _ in range(4))
    A, B, C = rand01(n, k), rand01(k, m), rand01(m, p)
    same += bool_product(A, B) == [[int(v > 0) for v in r] for r in int_product(A, B)]
    assoc += bool_product(bool_product(A, B), C) == bool_product(A, bool_product(B, C))
print("A⊙B == (AB > 0):", same, "of 2000;  (A⊙B)⊙C == A⊙(B⊙C):", assoc, "of 2000")

W ⊙ H = [[1, 1], [1, 0]]    W H = [[1, 2], [1, 0]]
X ∨ Y = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]    X ∧ Y = [[0, 0, 0], [0, 0, 1], [0, 0, 0]]
X ⊙ Y = [[0, 1, 1], [1, 1, 1], [0, 1, 0]]    Y ⊙ X = [[0, 1, 1], [1, 0, 1], [1, 1, 1]]
A⊙B == (AB > 0): 2000 of 2000;  (A⊙B)⊙C == A⊙(B⊙C): 2000 of 2000

৪ · Adjacency matrix আর Boolean power — k ধাপে কোথায় পৌঁছানো যায়

বাজারঘরের ভ্যান কিছু জেলার মধ্যে একমুখী রুটে চলে: ঢাকা → চট্টগ্রাম, ঢাকা → রাজশাহী, চট্টগ্রাম → খুলনা, চট্টগ্রাম → সিলেট, রাজশাহী → খুলনা, খুলনা → ঢাকা. সিলেট থেকে কোনো ভ্যান ছাড়ে না। প্রশ্ন: ঠিক দুটি রুট পেরিয়ে ঢাকা থেকে কোথায় যাওয়া যায়? রাজশাহী থেকে সিলেটে পার্সেল পাঠাতে সবচেয়ে কম কয়টি রুট লাগে? এমন জেলা-জোড়া কি আছে, যেখানে কখনোই পৌঁছানো যায় না? ছোট নেটওয়ার্কে চোখে দেখা যায়, কিন্তু ৬৪টি জেলার নেটওয়ার্কে একটি পদ্ধতি লাগে। সেই পদ্ধতি Boolean power.

গ্রাফের পূর্ণ তত্ত্ব আসবে মডিউল ১০-এ (পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem”), আর adjacency matrix বনাম adjacency list-এর তুলনা পর্ব ৫৮ “গ্রাফের representation আর isomorphism”-এ; প্রোগ্রামে তাদের উপস্থাপন DSA কোর্সের পর্ব ৩৯-এ। এখানে আমাদের শুধু তীর আর walk লাগবে।

1কলাম: DHK CTG KHL RAJ SYL2DHK সারি: 0 1 0 1 03CTG সারি: 0 0 1 0 14RAJ সারি: 0 0 1 0 05এক ধাপ বনাম ঠিক দুই ধাপ

প্রমাণ (k-এর ওপর mathematical induction, পর্ব ১০):

1. ভিত্তি k = 1: A^[1] = I ⊙ A = A, আর দৈর্ঘ্য 1-এর walk মানে একটি তীর; a_ij = 1 ঠিক তখন। (খ)-তেও a_ij হলো দৈর্ঘ্য 1-এর walk-এর সংখ্যা (0 বা 1). — adjacency matrix-এর সংজ্ঞা
2. Inductive hypothesis: কোনো k ≥ 1-এর জন্য দাবি দুটি সব i, j-তে সত্য ধরি। — অনুমান
3. দৈর্ঘ্য k + 1-এর প্রতিটি walk v_i = u₀, …, u_k, u_k+1 = v_j-কে ঠিক একভাবে ভাঙা যায়: v_i থেকে u_k = v_t-তে দৈর্ঘ্য k-এর একটি walk, তারপর v_t → v_j তীর। উল্টোভাবে এমন যেকোনো জোড়া জুড়লে দৈর্ঘ্য k + 1-এর walk হয়। — শেষ ধাপ আলাদা করা
4. (ক) তাই দৈর্ঘ্য k + 1-এর walk আছে ⇔ কোনো t-তে (A^[k])_it = 1 আর a_tj = 1 ⇔ (A^[k] ⊙ A)_ij = (A^[k+1])_ij = 1. — hypothesis আর ⊙-এর সংজ্ঞা
5. (খ) ধাপ ৩-এর ভাঙন এক-এক মিল, তাই walk-এর সংখ্যা = ∑_t (v_i থেকে v_t-তে দৈর্ঘ্য k-এর walk-এর সংখ্যা) × a_tj = ∑_t (A^k)_ita_tj = (A^k+1)_ij. ∎ — যোগ আর গুণের নিয়ম, hypothesis

এবার শেষ প্রশ্ন: কোন জোড়ায় কোনো দৈর্ঘ্যের walk আছে? অসীম সংখ্যক k দেখা সম্ভব নয়, কিন্তু দরকারও নেই।

প্রমাণ:

1. v_i থেকে v_j-তে walk-গুলোর মধ্যে সবচেয়ে ছোটটি নিই, দৈর্ঘ্য m; well-ordering নীতি (পর্ব ১১) বলে এমন একটি আছে। — well-ordering
2. ধরি m > n. তাহলে walk-এর m + 1টি অবস্থানের মধ্যে u₁, …, u_m এই m > n-টিতে মাত্র n-টি শীর্ষবিন্দু, তাই pigeonhole অনুযায়ী কোনো শীর্ষবিন্দু দুবার আসে: u_p = u_q, 1 ≤ p < q ≤ m. — pigeonhole (পর্ব ১৬)
3. u_p+1, …, u_q অংশটি কেটে দিলে v_i থেকে v_j-তে দৈর্ঘ্য m − (q − p) < m-এর একটি walk পাই, আর তার দৈর্ঘ্য ≥ 1, কারণ u₁ থেকে গোনা হয়েছে বলে প্রথম তীরটি থাকে। এটি সবচেয়ে ছোট হওয়ার বিরোধী। — proof by contradiction
4. তাই m ≤ n, আর উপপাদ্য ৪.২(ক) অনুযায়ী (A^[m])_ij = 1, ফলে (A^*)_ij = 1. উল্টো দিক সরাসরি ৪.২ থেকে। ∎

A^*-কে বলে A-এর relation-এর transitive closure. এটি বের করার দ্রুততর উপায় Warshall-এর algorithm, যা আসবে পর্ব ৫৪ “Relation-এর closure আর Warshall-এর algorithm”-এ; সেখানে এই উপপাদ্যই শুরুর বিন্দু। নিচের ব্লক আমাদের নেটওয়ার্কে k = 1 থেকে 5 পর্যন্ত Boolean power, “k ধাপের মধ্যে” কতগুলো জোড়া পৌঁছানো যায়, আর ঢাকা থেকে walk-এর সংখ্যা (সাধারণ ঘাত) ছাপে।

names = ["DHK", "CTG", "KHL", "RAJ", "SYL"]
routes = [("DHK", "CTG"), ("DHK", "RAJ"), ("CTG", "KHL"),
          ("CTG", "SYL"), ("RAJ", "KHL"), ("KHL", "DHK")]
n = len(names)
A = [[0] * n for _ in range(n)]
for u, v in routes:
    A[names.index(u)][names.index(v)] = 1

def bprod(X, Y):
    return [[int(any(X[i][t] and Y[t][j] for t in range(n))) for j in range(n)]
            for i in range(n)]

def iprod(X, Y):
    return [[sum(X[i][t] * Y[t][j] for t in range(n)) for j in range(n)]
            for i in range(n)]

def rows(M):
    return " ".join("".join(map(str, r)) for r in M)

P, C, R = A, A, A        # Boolean power, integer power, "within k steps"
for k in range(1, 6):
    if k > 1:
        P, C = bprod(P, A), iprod(C, A)
        R = [[R[i][j] | P[i][j] for j in range(n)] for i in range(n)]
    print(f"k={k}  A^[{k}] = {rows(P)}   within {k}: {sum(map(sum, R))} pairs")
    if k <= 3:
        print(f"      walks from DHK of length {k}:", dict(zip(names, C[0])))
never = [(names[i], names[j]) for i in range(n) for j in range(n) if not R[i][j]]
print("never reachable:", never)

k=1  A^[1] = 01010 00101 10000 00100 00000   within 1: 6 pairs
      walks from DHK of length 1: {'DHK': 0, 'CTG': 1, 'KHL': 0, 'RAJ': 1, 'SYL': 0}
k=2  A^[2] = 00101 10000 01010 10000 00000   within 2: 12 pairs
      walks from DHK of length 2: {'DHK': 0, 'CTG': 0, 'KHL': 2, 'RAJ': 0, 'SYL': 1}
k=3  A^[3] = 10000 01010 00101 01010 00000   within 3: 19 pairs
      walks from DHK of length 3: {'DHK': 2, 'CTG': 0, 'KHL': 0, 'RAJ': 0, 'SYL': 0}
k=4  A^[4] = 01010 00101 10000 00101 00000   within 4: 20 pairs
k=5  A^[5] = 00101 10000 01010 10000 00000   within 5: 20 pairs
never reachable: [('SYL', 'DHK'), ('SYL', 'CTG'), ('SYL', 'KHL'), ('SYL', 'RAJ'), ('SYL', 'SYL')]

৫ · গুণের খরচ — বন্ধনী কোথায় বসাবেন

উপপাদ্য ২.২(ক) বলে (AB)C = A(BC): ফল একই। কিন্তু কম্পিউটারের কাছে দুটি পথের খরচ একই নয়। একটি p × q matrix-কে q × r matrix দিয়ে সংজ্ঞা অনুযায়ী গুণ করলে ফলের pr-টি ঘরের প্রতিটিতে q-টি সংখ্যা-গুণ লাগে।

প্রমাণ: (ক) ফলের প্রতিটি ঘর ∑_t=1^q a_itb_tj: q-টি গুণ আর q − 1টি যোগ; ঘর pr-টি, গুণের নিয়মে মোট pqr আর pr(q − 1). (খ) যেকোনো বন্ধনীতে শেষ গুণটি দুটি অংশের মধ্যে: (A₁⋯A_k)(A_k+1⋯A_n), কোনো 1 ≤ k ≤ n − 1-এর জন্য। বাম অংশের P(k) আর ডান অংশের P(n − k) উপায় স্বাধীনভাবে মেলে, আর ভিন্ন k ভিন্ন বন্ধনী দেয়; তাই যোগ-গুণের নিয়মে সূত্রটি। ∎

P(n)-এর মানগুলো 1, 1, 2, 5, 14, 42, …: এগুলো বিখ্যাত Catalan সংখ্যা (n − 1-তম), যার closed form আর আরও অনেক রূপ আসবে পর্ব ৫০ “বিশেষ সংখ্যা — Catalan, Stirling আর partition”-এ। এরা প্রায় 4ⁿ হারে বাড়ে, তাই সব বন্ধনী একে একে দেখা বড় n-এ অবাস্তব।

1A: 10 × 302B: 30 × 53C: 5 × 604পথ ১: (AB)C5পথ ২: A(BC)

চারটি matrix হলে বন্ধনী পাঁচভাবে বসে, আর তাদের খরচের পার্থক্য আরও বড় হতে পারে। সবচেয়ে সস্তা বন্ধনী খোঁজার সমস্যাকে বলে matrix chain multiplication. উপপাদ্য ৫.১(খ)-এর যুক্তি থেকেই সমাধান আসে: শেষ গুণ কোথায় হবে (k), প্রতিটি সম্ভাবনায় দুই অংশের সবচেয়ে কম খরচ আর শেষ গুণের খরচ যোগ করে সর্বনিম্নটি নিন। একই উপসমস্যা বারবার আসে বলে উত্তরগুলো মনে রেখে কাজ করার এই কৌশলের নাম dynamic programming; এর algorithm আর টেবিল DSA কোর্সের পর্ব ৫৪-এ। নিচের ব্লক stepper-এর হিসাব, চারটি matrix-এর পাঁচটি বন্ধনীর খরচ, DP-র উত্তর আর P(n)-এর মান ছাপে।

from functools import lru_cache
from math import comb

def cost(p, q, r):        # (p x q) times (q x r) needs p*q*r scalar multiplications
    return p * q * r

print("A 10x30, B 30x5, C 5x60")
print("  (AB)C:", cost(10, 30, 5) + cost(10, 5, 60),
      "  A(BC):", cost(30, 5, 60) + cost(10, 30, 60))

dims = [20, 2, 30, 12, 8]     # M1 20x2, M2 2x30, M3 30x12, M4 12x8

def orders(i, j):             # every bracketing of Mi..Mj with its cost
    if i == j:
        return [(f"M{i + 1}", 0)]
    out = []
    for k in range(i, j):
        for ls, lc in orders(i, k):
            for rs, rc in orders(k + 1, j):
                out.append((f"({ls}{rs})", lc + rc + dims[i] * dims[k + 1] * dims[j + 1]))
    return out

for s, c in sorted(orders(0, 3), key=lambda x: x[1]):
    print(f"  {s:16} {c:6}")

@lru_cache(maxsize=None)
def best(i, j):               # dynamic programming over sub-chains Mi..Mj
    if i == j:
        return 0
    return min(best(i, k) + best(k + 1, j) + dims[i] * dims[k + 1] * dims[j + 1]
               for k in range(i, j))

print("DP minimum:", best(0, 3))
print("bracketings for n = 1..10 matrices:",
      [comb(2 * (n - 1), n - 1) // n for n in range(1, 11)])

A 10x30, B 30x5, C 5x60
  (AB)C: 4500   A(BC): 27000
  (M1((M2M3)M4))     1232
  ((M1(M2M3))M4)     3120
  (M1(M2(M3M4)))     3680
  ((M1M2)(M3M4))     8880
  (((M1M2)M3)M4)    10320
DP minimum: 1232
bracketings for n = 1..10 matrices: [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

Strassen — আটের বদলে সাত

উপপাদ্য ৫.১(ক) সংজ্ঞা অনুযায়ী গুণের খরচ; প্রশ্ন হলো সংজ্ঞাটি কি একমাত্র উপায়? দুটি n × n matrix-এ সংজ্ঞা লাগে n³টি গুণ। Volker Strassen ১৯৬৯ সালে দেখান, দুটি 2 × 2 matrix (বা block) সাতটি গুণে (আটটির বদলে, কিছু বাড়তি যোগ-বিয়োগের বিনিময়ে) গুণ করা যায়; এটি বারবার অর্ধেক আকারে প্রয়োগ করলে মোট খরচ মোটামুটি n^{log₂ 7} ≈ n^2.81. এই Strassen-এর algorithm-এর বিস্তারিত আর recurrence DSA কোর্সের পর্ব ৪৯-এ। বাস্তবে বড় matrix ছাড়া সাধারণ পদ্ধতিই প্রায়ই দ্রুত, আর দশমিক সংখ্যায় Strassen-এর গোলমাল (rounding error) একটু বেশি হতে পারে, তাই লাইব্রেরিগুলো সাধারণত সংজ্ঞার পদ্ধতিই খুব যত্নে সাজিয়ে ব্যবহার করে। উপপাদ্য ৩.২-এর জন্য 0-1 matrix-এর Boolean product-ও যেকোনো দ্রুত পূর্ণসংখ্যা-গুণ দিয়ে করা যায়: সাধারণ গুণফল বের করে ধনাত্মক ঘরকে 1 করলেই হলো।

৬ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় এই বিষয়ের যে ধাঁচের অঙ্ক আসে, তার তিনটি পূর্ণ সমাধান। প্রতিটি সংখ্যা উপরের ব্লক বা scratch-এ Python দিয়ে মেলানো।

অঙ্ক ১: X = [[1, 0, 1], [0, 1, 1], [1, 0, 0]], Y = [[0, 1, 0], [1, 0, 1], [0, 1, 1]]. X ∨ Y, X ∧ Y, X ⊙ Y আর Y ⊙ X বের করুন

1. Join আর meet ঘরে ঘরে: X ∨ Y-এর প্রতিটি ঘর 1 (প্রতিটি অবস্থানে X বা Y-এর অন্তত একটি 1). X ∧ Y-এ শুধু (2, 3) ঘর 1, কারণ একমাত্র সেখানেই দুটিই 1.
2. X ⊙ Y, সারি ধরে: X-এর সারি 1 = 1 0 1, তাই Y-এর সারি 1 আর 3-এর join: 010 ∨ 011 = 011. সারি 2 = 0 1 1: Y-এর সারি 2 আর 3: 101 ∨ 011 = 111. সারি 3 = 1 0 0: শুধু Y-এর সারি 1: 010. তাই X ⊙ Y = [[0, 1, 1], [1, 1, 1], [0, 1, 0]].
3. Y ⊙ X: Y-এর সারি 1 = 0 1 0: X-এর সারি 2 = 011. সারি 2 = 1 0 1: X-এর সারি 1 আর 3: 101 ∨ 100 = 101. সারি 3 = 0 1 1: X-এর সারি 2 আর 3: 011 ∨ 100 = 111. তাই Y ⊙ X = [[0, 1, 1], [1, 0, 1], [1, 1, 1]] ≠ X ⊙ Y.

কৌশলটি মনে রাখুন: (A ⊙ B)-এর i-তম সারি = A-এর i-তম সারিতে যেখানে যেখানে 1, B-এর সেই সারিগুলোর join. ঘরে ঘরে হিসাবের চেয়ে দ্রুত, আর ভুল কম।

অঙ্ক ২: M1 20 × 2, M2 2 × 30, M3 30 × 12, M4 12 × 8. সবচেয়ে কম সংখ্যা-গুণের বন্ধনী কোনটি?

1. বন্ধনী P(4) = 5টি। প্রতিটির খরচ: (((M1M2)M3)M4) = 1200 + 7200 + 1920 = 10320; ((M1M2)(M3M4)) = 1200 + 2880 + 4800 = 8880; ((M1(M2M3))M4) = 720 + 480 + 1920 = 3120; (M1((M2M3)M4)) = 720 + 192 + 320 = 1232; (M1(M2(M3M4))) = 2880 + 480 + 320 = 3680.
2. উত্তর: M1((M2M3)M4), 1232টি গুণ। §৫-এর ব্লকের তালিকার সঙ্গে প্রতিটি সংখ্যা মেলে।

অঙ্ক ৩: §৪-এর ভ্যান-নেটওয়ার্কে রাজশাহী থেকে সিলেটে সবচেয়ে কম কয় ধাপে যাওয়া যায়?

সবচেয়ে ছোট k বের করতে হবে যাতে (A^[k])_{RAJ, SYL} = 1. রাজশাহীর সারি: A-তে 00100 (শুধু খুলনা), A^[2]-এ 10000 (ঢাকা), A^[3]-এ 01010 (চট্টগ্রাম, রাজশাহী), A^[4]-এ 00101 (খুলনা, সিলেট)। উত্তর 4: রাজশাহী → খুলনা → ঢাকা → চট্টগ্রাম → সিলেট. প্রতিটি সারি এক ধাপ আগের সারিতে যেখানে 1, A-এর সেই সারিগুলোর join; অঙ্ক ১-এর কৌশলই।

প্রমাণের ভুল ধরুন: “A^[2] হলো দুই ধাপের মধ্যে reachability”

একজন লিখলেন: “দাবি: যেকোনো directed graph-এ (A^[2])_ij = 1 ⇔ v_i থেকে v_j-তে বড়জোর দুই ধাপে যাওয়া যায়। প্রমাণ: উপপাদ্য ৪.২ বলে A^[2] দুই ধাপের walk চিনে নেয়; আর এক ধাপের রুট থাকলে তার পরে আরেকটি রুট নিলে দুই ধাপ হয়। ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: “তার পরে আরেকটি রুট” সবসময় থাকে না। §৪-এর নেটওয়ার্কে ঢাকা → চট্টগ্রাম এক ধাপে যায়, কিন্তু (A^[2])_{DHK, CTG} = 0: ঠিক দুই ধাপে চট্টগ্রামে পৌঁছানোর কোনো walk নেই। প্রমাণটি এমন একটি ধাপ নিঃশব্দে ধরে নিয়েছে, যা প্রতিটি শীর্ষবিন্দুতে একটি loop (নিজের দিকে তীর) থাকলে তবেই সত্য। সঠিক দাবি: “বড়জোর দুই ধাপ” ⇔ (A ∨ A^[2])_ij = 1, বা সমতুল্যভাবে ((A ∨ I)^[2])_ij = 1 (i ≠ j-এর জন্য)। শিক্ষা: “ঠিক k” আর “বড়জোর k” আলাদা quantifier, আর একটি ছোট counterexample-ই এমন প্রমাণ বাতিল করে।

৭ · AI-এর যুগে — matrix-এর হিসাব আর প্রমাণ যাচাই

AI সহকারীকে একটি Boolean product বা matrix chain-এর খরচ জিজ্ঞেস করলে উত্তর সাধারণত দ্রুত আর পরিপাটি আসে। কিন্তু এখানে ছোট ভুলই বড় ফল বদলায়, আর AI-এর কিছু ভুল নিয়মিত:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি matrix-এর আকার আর ভেতরের মাপ মিলিয়েছি
• Boolean product-এর ফলের সব ঘর 0 বা 1, আর সাধারণ গুণফলের ধনাত্মক ঘরের সঙ্গে মেলে
• প্রমাণে কোথাও নিঃশব্দে AB = BA ধরা হয়নি; transpose-এ ক্রম উল্টেছে
• “ঠিক k” আর “বড়জোর k” আলাদা রাখা হয়েছে; একটি ছোট graph-এ হাতে মিলিয়েছি
• গুণের খরচ pqr নিয়মে নিজে গুনেছি, আর ছোট chain-এ brute force দিয়ে মিলিয়েছি
• উল্লেখিত উপপাদ্যের শর্ত (0-1 matrix, বর্গ matrix, n শীর্ষবিন্দু) আর ইতিহাসের সাল বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

সবচেয়ে সস্তা প্রথম পরীক্ষা: AI যে matrix ফল দিল, সেটি §৩-এর bool_product বা §২-এর mul দিয়ে নিজে চালিয়ে মেলান। একটি ঘরের অমিলই পুরো উত্তরকে সন্দেহজনক করে।