Chapter 2.2 — Gaussian Elimination ও RREF (গাউসিয়ান এলিমিনেশন)¶

🎯 এই chapter-এ যা শিখবে¶

Elementary Row Operations(এলিমেন্টারি রো অপারেশন) — মাত্র তিনটা বৈধ চাল, যেগুলো সমাধান সেট অটুট রাখে
Gaussian Elimination(গাউসিয়ান এলিমিনেশন) — সেই তিন চাল দিয়ে যেকোনো সিস্টেমকে সরল করার যান্ত্রিক অ্যালগরিদম, প্রতি ধাপের matrix state সহ
Reduced Row Echelon Form / RREF(রিডিউসড রো এশেলন ফর্ম) — একটা matrix-এর "সবচেয়ে পরিষ্কার রূপ", তার চারটা নিয়ম
Pivot(পিভট) আর Free Variable(মুক্ত চলক) চেনা — আর RREF দেখে এক নজরে বলে দেওয়া সমাধান \(0\), \(1\) না \(\infty\)
হাতে ও কোডে RREF বের করা — এবং কেন প্রতিটা ধাপ নিরাপদ তার প্রমাণ

🖼️ এক ছবিতে মূল idea¶

Step by step elimination

একটা \(3\times 3\) সিস্টেমের augmented matrix, প্রতি ধাপে একটা করে row operation — নিচের-বাঁ অংশ ধীরে ধীরে শূন্য (সাদা) হয়ে সিঁড়ির মতো আকার নিচ্ছে, শেষে RREF থেকে উত্তর \(x=2, y=2, z=3\) সরাসরি পড়ে নেওয়া যায়।

১. কি? (What)¶

জট ছাড়ানোর অ্যালগরিদম¶

সুতার বল জট পাকিয়ে গেলে তুমি কী করো? এলোমেলো টানাটানি না করে একবারে একটা গিঁট খোলো — এমনভাবে, যেন নতুন গিঁট না লাগে। Gaussian elimination ঠিক তাই: linear system-এর জট (variable-গুলো সব equation-এ জড়াজড়ি করে আছে) ছাড়ানো হয় একবারে একটা সংখ্যা শূন্য করে — আর "নতুন গিঁট না লাগা"-র গ্যারান্টি দেয় তিনটা নিরাপদ চাল।

আগের chapter-এর Property 4 মনে করো — সমাধান সেট না বদলানো তিনটা কাজ। Augmented matrix-এর ভাষায় এদের নাম Elementary Row Operations (ERO):

#	চাল	সংকেত	উল্টো চাল
1	Swap(অদলবদল): দুটো row-এর জায়গা বদল	\(R_i \leftrightarrow R_j\)	নিজেই
2	Scale(মাপবদল): একটা row-কে nonzero \(c\) দিয়ে গুণ	\(R_i \leftarrow cR_i\)	\(R_i \leftarrow \frac{1}{c}R_i\)
3	Add(যোগ): এক row-এর গুণিতক আরেক row-তে যোগ	\(R_i \leftarrow R_i + cR_j\)	\(R_i \leftarrow R_i - cR_j\)

প্রতিটা চালের উল্টো চাল আছে — তাই কোনো তথ্য হারায় না, সমাধান সেট ছবির মতো অটুট থাকে। দুটো matrix-কে বলে Row Equivalent(রো ইকুইভ্যালেন্ট) (লেখা হয় \(\sim\)) যদি EROs-এর একটা সিরিজ দিয়ে একটাকে অন্যটা বানানো যায়।

লক্ষ্য: Echelon — সিঁড়ির আকার¶

Elimination-এর লক্ষ্য হলো matrix-টাকে সিঁড়ির (echelon) আকারে আনা — প্রতিটা row-এর প্রথম nonzero সংখ্যা আগের row-এরটার চেয়ে ডানে। প্রতিটা row-এর সেই প্রথম nonzero entry-র (RREF-এ যেটা 1 বানানো হয়) নাম Pivot(পিভট)।

আর চূড়ান্ত, সবচেয়ে পালিশ-করা রূপের নাম Reduced Row Echelon Form (RREF)। একটা matrix RREF-এ আছে যদি:

প্রতিটা nonzero row-এর প্রথম nonzero entry হলো \(1\) (pivot);
প্রতিটা pivot তার column-এ একা — উপরে-নিচে সব শূন্য;
প্রতিটা pivot আগের row-এর pivot-এর ডানে (সিঁড়ি ডানে নামে);
সব-শূন্য row-রা একেবারে নিচে।

যে column-এ pivot আছে সেটা Pivot Column, যে variable-এর column-এ pivot নেই সে হলো Free Variable — তার মান তুমি খুশিমতো বেছে নিতে পারো (বিস্তারিত Chapter 2.4-এ)।

একটা আশ্চর্য সত্য (uniqueness): যে পথেই EROs করো না কেন — আগে যেটা খুশি, পরে যেটা খুশি — একটা matrix-এর RREF একটাই। তাই RREF হলো সিস্টেমের "fingerprint": দুজন মানুষ ভিন্ন পথে গিয়েও একই RREF-এ পৌঁছাবে।

২. দেখতে কেমন?¶

Geometry: লাইন নড়ে, সমাধান নড়ে না¶

Lines change, solution stays

Elimination-এর প্রতি ধাপে equation-রা (লাইনগুলো) বদলে যায় — কিন্তু তাদের ছেদবিন্দু \((4,6)\) এক চুলও নড়ে না। শেষ ধাপে লাইন দুটো দাঁড়িয়ে যায় axis-বরাবর (\(x=4\), \(y=6\)) — উত্তরটা তখন খালি চোখেই পড়া যায়।

এটাই Gaussian elimination-এর আত্মা: সিস্টেম বদলাও, সমাধান নয় — যতক্ষণ না সিস্টেমটা এত সরল হয় যে উত্তর নিজে থেকেই বেরিয়ে আসে।

RREF-এর শারীরস্থান¶

Anatomy of RREF

একটা RREF matrix-এর অঙ্গপ্রত্যঙ্গ: লাল বাক্সে pivot-রা (প্রতিটা \(1\), নিজের column-এ একা, সিঁড়ি বেয়ে ডানে নামছে), সবুজ চিহ্নিত free column-রা, আর নিচে শূন্য row।

৩. কোথায় ইউজ হয়?¶

সব linear solver-এর হৃৎপিণ্ড: np.linalg.solve, MATLAB-এর \, R-এর solve — ভেতরে সবাই elimination-এরই পালিশ-করা রূপ (LU, পরের chapter) চালায়। বিশ্বের সুপারকম্পিউটারের র‍্যাঙ্কিং (TOP500) পর্যন্ত মাপা হয় elimination-জাতীয় কাজের গতি দিয়ে (LINPACK benchmark)!
Rank(র‍্যাঙ্ক) নির্ণয়: RREF-এর pivot-সংখ্যাই matrix-এর rank — data matrix-এ কতটুকু "স্বাধীন তথ্য" আছে তার মাপ (Part IV-এ পুরো গল্প)।
Inverse বের করা: \((A|I)\)-তে elimination চালিয়ে \((I|A^{-1})\) — Part III-এ দেখবে।
Determinant-এর দ্রুত হিসাব: সূত্র মুখস্থের বদলে elimination দিয়ে (Part VI)।
ML/Data Science-এ: feature-দের মধ্যে redundancy (multicollinearity) ধরা, linear regression-এর equation solve করা, network/circuit simulation — সব রাস্তাই এই অ্যালগরিদমে এসে মেশে।

একটা মজার তথ্য: অ্যালগরিদমটা Gauss-এর নামে হলেও চীনা গণিতগ্রন্থ নয় অধ্যায়ে গাণিতিক শিল্প-তে (আনুমানিক ২০০০ বছর আগে) প্রায় একই পদ্ধতি ছিল!

৪. Properties¶

Property 1 — EROs সমাধান সেট বদলায় না (মিনি-প্রমাণ)¶

প্রতিটা ERO-র উল্টো ERO আছে (উপরের টেবিল)। পুরনো সিস্টেমের যেকোনো সমাধান নতুনটাকেও মানে (যোগ/গুণ সত্য equation-দের সত্যই রাখে); আবার উল্টো চাল প্রয়োগ করলে নতুনটার সমাধান পুরনোটাকে মানে। দুই সেট পরস্পরের ভেতরে — অতএব সমান। \(\blacksquare\)

⚠️ Scale-এ \(c\ne 0\) শর্তটা এখানেই জরুরি: \(0\) দিয়ে গুণ করলে row-টা \(0=0\) হয়ে যায় — এক equation-এর তথ্য চিরতরে মুছে যায়, উল্টো চাল বলে কিছু থাকে না।

Property 2 — অ্যালগরিদমটা নিজে¶

Elimination flowchart

পুরো অ্যালগরিদম এক নজরে: নিচের দিকে ঝাড়ু দাও (forward pass), তারপর উপরের দিকে (backward pass)।

শব্দে লিখলে:

বাঁ থেকে প্রথম যে column-এ nonzero entry আছে সেটা ধরো; দরকারে swap করে nonzero-টাকে উপরের row-এ আনো — এটা pivot;
Pivot row-কে scale করে pivot-কে \(1\) বানাও;
Add-চাল দিয়ে pivot-এর নিচের সব entry শূন্য করো;
এক row নিচে, pivot column-এর ডানে গিয়ে repeat — row শেষ না হওয়া পর্যন্ত (এ পর্যন্ত এসে থামলে যা পাও তার নাম Row Echelon Form);
Backward pass: ডান থেকে বাঁয়ে, প্রতিটা pivot-এর উপরের entry-ও শূন্য করো → RREF।

Property 3 — RREF থেকে রায় পড়া¶

RREF verdict

Augmented matrix-এর RREF-এ তিন রকম দৃশ্য: (বাঁয়ে) প্রতিটা variable column-এ pivot → ঠিক ১টা সমাধান; (মাঝে) free column আছে কিন্তু কোনো গোলমাল নেই → অসীম সমাধান; (ডানে) কোনো row বলছে \(0=1\) → সমাধান নেই।

নিয়মটা মুখস্থ নয়, বোঝার:

\(\left(0\ 0\ \cdots\ 0\,|\,1\right)\) row মানে \(0x_1+\cdots+0x_k = 1\), অসম্ভব → inconsistent;
গোলমাল নেই + প্রতি variable-এ pivot → প্রতিটা variable-এর মান নির্দিষ্ট → ঠিক ১টা;
গোলমাল নেই + free variable আছে → free-দের যেকোনো মানে একটা করে সমাধান → অসীম।

Property 4 — Pivot-সংখ্যার সীমা¶

Pivot-রা ভিন্ন ভিন্ন row আর ভিন্ন ভিন্ন column দখল করে, তাই pivot-সংখ্যা \(\le \min(r, k)\) (row-সংখ্যা \(r\), variable \(k\))। ফল: variable-এর চেয়ে equation কম হলে (\(r<k\)) সব column-এ pivot অসম্ভব — consistent হলে সমাধান অবধারিতভাবে অসীম। "লম্বাটে-চওড়া" সিস্টেম কখনো ঠিক ১টা উত্তর দেয় না!

৫. Intuition — কেন সত্য?¶

কেন নিচের-বাঁ কোণ থেকে শুরু?¶

Elimination আসলে তথ্য পুনর্বিন্যাস। শুরুতে প্রতিটা equation-এ সব variable মিশে আছে; আমরা চাই প্রতিটা equation শুধু একটা variable-এর কথা বলুক ("\(x=2\)")। ধাপগুলো এমনভাবে সাজানো যেন আগের করা শূন্যরা পরে নষ্ট না হয়: pivot-এর নিচে শূন্য করার সময় pivot column-এর বাঁয়ের সব column-এ ইতিমধ্যেই শূন্য — তাই Add-চাল বাঁদিকের শূন্যদের শূন্যই রাখে (\(c\cdot 0 + 0 = 0\))। সিঁড়ি তাই কখনো ভাঙে না। Backward pass-ও একই কারণে নিরাপদ: pivot-এর উপরে শূন্য করার সময় সেই pivot-এর row-এ বাঁদিকে সব শূন্য, তাই আগের pivot column-গুলো অক্ষত থাকে।

RREF কেন সিস্টেমের "উত্তরপত্র"?¶

RREF-এ পৌঁছালে প্রতিটা pivot row পড়া যায় এভাবে: "pivot variable = (ধ্রুবক) − (free variable-দের মিশ্রণ)"। free variable না থাকলে সরাসরি "pivot variable = ধ্রুবক"। অর্থাৎ RREF কেবল সরল রূপ না — সে সমাধানটা স্পষ্ট অক্ষরে লিখে দেয়। এ কারণেই RREF-এর চেয়ে বেশি সরল করার কিছু বাকি থাকে না, আর এ কারণেই সে unique: একই সমাধান সেটের "সম্পূর্ণ বিবরণ" তো একটাই হবে।

Column picture-এ elimination কী করে?¶

মজার প্রশ্ন: row operation তো row-দের উপর চলে — column picture-এর কী হয়? Column-রা বদলে যায় ঠিকই, কিন্তু column-দের মধ্যেকার সম্পর্ক (কোনটা কোনটার কত গুণ, কোন মিশ্রণে শূন্য হয়) হুবহু অটুট থাকে। যেমন col₃ = 2·col₁ + col₂ সম্পর্কটা elimination-এর আগে-পরে সমান সত্য। এই পর্যবেক্ষণই Part IV-এ rank আর linear independence-এর হিসাবের প্রাণ।

৬. Code-এ কেমনে লিখে¶

RREF এক লাইনে দেয় SymPy: sympy.Matrix(...).rref()। কিন্তু আমরা আগে নিজের হাতে বানাই — প্রতিটা ধাপ প্রিন্ট করে:

import numpy as np

def rref_steps(M, verbose=True):
    """Augmented matrix M-কে RREF-এ নাও, প্রতি ধাপ দেখাও।"""
    A = M.astype(float).copy()
    r, c = A.shape
    pivots = []
    row = 0
    for col in range(c - 1):              # শেষ column b — ওখানে pivot নয়
        # ১) এই column-এ pivot খোঁজো (row থেকে নিচে সবচেয়ে বড়টা — নিরাপদ)
        best = row + np.argmax(np.abs(A[row:, col]))
        if np.isclose(A[best, col], 0):
            continue                      # পুরো column শূন্য → free column
        if best != row:
            A[[row, best]] = A[[best, row]]           # SWAP
            if verbose: print(f"R{row+1} <-> R{best+1}\n", A, "\n")
        A[row] = A[row] / A[row, col]                 # SCALE: pivot = 1
        if verbose: print(f"R{row+1} /= pivot\n", A, "\n")
        for i in range(r):                            # ADD: column সাফ
            if i != row and not np.isclose(A[i, col], 0):
                f = A[i, col]
                A[i] = A[i] - f * A[row]
                if verbose: print(f"R{i+1} -= {f:g} R{row+1}\n", A, "\n")
        pivots.append(col)
        row += 1
        if row == r:
            break
    return A, pivots

M = np.array([[1., 2., 1., 9.],
              [2., 6., 1., 19.],
              [1., 1., 4., 16.]])
R, piv = rref_steps(M)
print("RREF:\n", R, "\npivot columns:", piv)

শেষ output:

RREF:
 [[1. 0. 0. 2.]
 [0. 1. 0. 2.]
 [0. 0. 1. 3.]]
pivot columns: [0, 1, 2]

প্রতিটা variable column-এ pivot → ঠিক ১টা সমাধান: \((2, 2, 3)\)। যাচাই করি লাইব্রেরি দিয়ে:

from sympy import Matrix
print(Matrix(M).rref())
# (Matrix([[1, 0, 0, 2], [0, 1, 0, 2], [0, 0, 1, 3]]), (0, 1, 2))

print(np.linalg.solve(M[:, :3], M[:, 3]))   # [2. 2. 3.] ✓

দুটো টেকনিক্যাল নোট: (১) কোডে pivot বাছতে column-এর সবচেয়ে বড় entry নিয়েছি (partial pivoting) — হাতের হিসাবে যা-খুশি nonzero নিলেই চলে, কিন্তু computer-এর ভাসমান-বিন্দুর জগতে ছোট pivot ভাগে বিপদ ঘটায় (Part VIII-এ ভয়ানক উদাহরণ পাবে); (২) np.isclose দিয়ে শূন্য-পরীক্ষা — floating point-এ == 0 লেখা প্রায়ই ভুল।

৭. Worked Examples¶

Example 1 — Unique solution, প্রতিটা ধাপের state সহ¶

সিস্টেম: \(\;x+2y+z=9,\quad 2x+6y+z=19,\quad x+y+4z=16\)

\[\left(\begin{array}{ccc|c}1&2&1&9\\2&6&1&19\\1&1&4&16\end{array}\right) \xrightarrow{R_2\leftarrow R_2-2R_1} \left(\begin{array}{ccc|c}1&2&1&9\\0&2&-1&1\\1&1&4&16\end{array}\right) \xrightarrow{R_3\leftarrow R_3-R_1} \left(\begin{array}{ccc|c}1&2&1&9\\0&2&-1&1\\0&-1&3&7\end{array}\right)\]

\[\xrightarrow{R_2\leftarrow \frac12 R_2} \left(\begin{array}{ccc|c}1&2&1&9\\0&1&-\tfrac12&\tfrac12\\0&-1&3&7\end{array}\right) \xrightarrow{R_3\leftarrow R_3+R_2} \left(\begin{array}{ccc|c}1&2&1&9\\0&1&-\tfrac12&\tfrac12\\0&0&\tfrac52&\tfrac{15}2\end{array}\right) \xrightarrow{R_3\leftarrow \frac25 R_3} \left(\begin{array}{ccc|c}1&2&1&9\\0&1&-\tfrac12&\tfrac12\\0&0&1&3\end{array}\right)\]

Forward pass শেষ — সিঁড়ি তৈরি। এবার backward pass (উপর দিকে ঝাড়ু):

\[\xrightarrow{\substack{R_1\leftarrow R_1-R_3\\ R_2\leftarrow R_2+\frac12 R_3}} \left(\begin{array}{ccc|c}1&2&0&6\\0&1&0&2\\0&0&1&3\end{array}\right) \xrightarrow{R_1\leftarrow R_1-2R_2} \left(\begin{array}{ccc|c}1&0&0&2\\0&1&0&2\\0&0&1&3\end{array}\right)\]

RREF থেকে সরাসরি: \(x=2,\ y=2,\ z=3\)। (এটাই opening figure-এর হিসাব।)

Example 2 — Free variable-ওয়ালা সিস্টেম¶

সিস্টেম: \(\;x + y + 2z = 4,\quad 2x + 2y + 5z = 9\)

\[\left(\begin{array}{ccc|c}1&1&2&4\\2&2&5&9\end{array}\right) \xrightarrow{R_2\leftarrow R_2-2R_1} \left(\begin{array}{ccc|c}1&1&2&4\\0&0&1&1\end{array}\right) \xrightarrow{R_1\leftarrow R_1-2R_2} \left(\begin{array}{ccc|c}1&1&0&2\\0&0&1&1\end{array}\right)\]

Pivot column: 1 আর 3; column 2 free → \(y\) free variable। RREF পড়ি: \(x + y = 2\) এবং \(z = 1\), অর্থাৎ

\[x = 2 - t,\quad y = t,\quad z = 1 \qquad (t \in \mathbb{R})\]

অসীম সমাধান — একটা গোটা লাইন। (\(t=0\) দিলে \((2,0,1)\), \(t=2\) দিলে \((0,2,1)\)... যাচাই করে দেখো!)

Example 3 — Inconsistent ধরা পড়ে যায়¶

সিস্টেম: \(\;x + 2y = 3,\quad 2x + 4y = 7\)

\[\left(\begin{array}{cc|c}1&2&3\\2&4&7\end{array}\right) \xrightarrow{R_2\leftarrow R_2-2R_1} \left(\begin{array}{cc|c}1&2&3\\0&0&1\end{array}\right)\]

দ্বিতীয় row: \(0x + 0y = 1\) — অসম্ভব। সমাধান নেই। লক্ষ করো, অ্যালগরিদম নিজে থেকেই খারাপ খবরটা প্রকাশ করে দিলো — আলাদা কোনো পরীক্ষা লাগেনি।

৮. Problems ও Solutions¶

Problem 1. নিচের কোন matrix-গুলো RREF-এ আছে? যেগুলো নেই, কোন নিয়ম ভেঙেছে বলো।

\[(a)\ \begin{pmatrix}1&0&3\\0&1&2\end{pmatrix}\quad (b)\ \begin{pmatrix}1&2&0\\0&0&2\end{pmatrix}\quad (c)\ \begin{pmatrix}0&1&0\\1&0&0\end{pmatrix}\quad (d)\ \begin{pmatrix}1&0&2\\0&0&0\\0&1&5\end{pmatrix}\quad (e)\ \begin{pmatrix}1&5&0&2\\0&0&1&7\\0&0&0&0\end{pmatrix}\]

Solution

(a) RREF ✓ — দুটো pivot (\(1\)), প্রত্যেকে column-এ একা, সিঁড়ি ডানে নামছে।

(b) নয় ✗ — দ্বিতীয় row-এর প্রথম nonzero entry \(2\), যা \(1\) নয় (নিয়ম ১ ভাঙা)। (\(R_2 \leftarrow \frac12 R_2\) করলেই RREF হয়ে যায়।)

(c) নয় ✗ — দ্বিতীয় row-এর pivot (column 1) প্রথম row-এর pivot-এর (column 2) বাঁয়ে — সিঁড়ি উল্টো (নিয়ম ৩ ভাঙা)। Swap করলেই ঠিক।

(d) নয় ✗ — শূন্য row মাঝখানে, নিচে নয় (নিয়ম ৪ ভাঙা)।

(e) RREF ✓ — pivot-রা column 1 ও 3-এ, প্রত্যেকে একা; column 2 আর 4 free; শূন্য row নিচে। (Pivot column-এ শূন্য-নয় এমন entry অন্য row-তে নেই, কিন্তু free column-এ যা-খুশি থাকতেই পারে!)

Problem 2. পুরো Gaussian elimination চালিয়ে RREF বের করো, প্রতিটা চাল লিখে:

\[\begin{aligned} x + 3y &= 7\\ 2x + 5y &= 12 \end{aligned}\]

Solution

\[\left(\begin{array}{cc|c}1&3&7\\2&5&12\end{array}\right) \xrightarrow{R_2\leftarrow R_2-2R_1} \left(\begin{array}{cc|c}1&3&7\\0&-1&-2\end{array}\right) \xrightarrow{R_2\leftarrow -R_2} \left(\begin{array}{cc|c}1&3&7\\0&1&2\end{array}\right) \xrightarrow{R_1\leftarrow R_1-3R_2} \left(\begin{array}{cc|c}1&0&1\\0&1&2\end{array}\right)\]

সমাধান: \(x=1,\ y=2\)। যাচাই: \(1+6=7\) ✓, \(2+10=12\) ✓।

Problem 3. RREF বের করে সমাধান সেট লেখো:

\[\begin{aligned} x + 2y - z &= 1\\ 2x + 4y - 2z &= 2\\ -x - 2y + z &= -1 \end{aligned}\]

Solution

\[\left(\begin{array}{ccc|c}1&2&-1&1\\2&4&-2&2\\-1&-2&1&-1\end{array}\right) \xrightarrow{\substack{R_2\leftarrow R_2-2R_1\\ R_3\leftarrow R_3+R_1}} \left(\begin{array}{ccc|c}1&2&-1&1\\0&0&0&0\\0&0&0&0\end{array}\right)\]

এটাই RREF! তিনটা equation আসলে একটাই ছিল (দ্বিতীয়টা প্রথমটার দ্বিগুণ, তৃতীয়টা ঋণাত্মক)। Pivot মাত্র ১টা (column 1); \(y, z\) free। সমাধান:

\[x = 1 - 2s + t,\quad y = s,\quad z = t \qquad (s, t \in \mathbb{R})\]

— দুই free parameter, অর্থাৎ সমাধান সেট একটা প্লেন (Chapter 2.4-এ এই geometry-রই গল্প)।

Problem 4. \(k\)-র কোন মানে সিস্টেমটার (a) ঠিক ১টা সমাধান, (b) কোনো সমাধান নেই, (c) অসীম সমাধান?

\[\begin{aligned} x + 2y &= 3\\ 3x + ky &= 9 \end{aligned}\]

Solution

Eliminate: \(R_2 \leftarrow R_2 - 3R_1\):

\[\left(\begin{array}{cc|c}1&2&3\\0&k-6&0\end{array}\right)\]

(a) \(k \ne 6\): দ্বিতীয় row-এ pivot আছে (\(k-6\ne0\)) → দুই column-এই pivot → ঠিক ১টা সমাধান। (\(R_2\) scale করলে \(y=0\), তারপর \(x=3\)।)

(b) কোনো \(k\)-তেই না! দ্বিতীয় row-এর ডানপাশও \(0\) হয়ে গেছে, তাই \(0=(\text{nonzero})\) কখনোই আসবে না।

(c) \(k = 6\): দ্বিতীয় row পুরো শূন্য → \(y\) free → অসীম সমাধান: \(x = 3-2t,\ y=t\)।

(লক্ষ করো: ডানপাশ \(9\)-এর জায়গায় \(10\) হলে (b)-র উত্তর হতো \(k=6\) — নিজে চেষ্টা করে দেখো।)

Problem 5. একটা \(3\times 5\) augmented matrix-এ (variable ৪টা) elimination শেষে ২টা pivot পাওয়া গেল এবং কোনো \(0=1\) row নেই। (a) free variable কয়টা? (b) সমাধান কয়টা? (c) সমাধান সেটের "মাত্রা" (free parameter-সংখ্যা) কত? (d) এমন সিস্টেমে সর্বোচ্চ কয়টা pivot সম্ভব ছিল?

Solution

(a) variable ৪টা, pivot ২টা → free variable \(4-2 = 2\)টা।

(b) consistent (কোনো গোলমাল-row নেই) + free variable আছে → অসীম।

(c) free parameter ২টা → সমাধান সেট দ্বিমাত্রিক (একটা প্লেন-জাতীয় বস্তু, \(\mathbb{R}^4\)-এর ভেতরে)।

(d) pivot \(\le \min(\text{rows}, \text{variables}) = \min(3,4) = 3\)টা। (Property 4)

Problem 6. তিনটা ERO-র প্রত্যেকটার জন্য দেখাও উল্টো চালটাও একটা ERO, এবং ব্যাখ্যা করো কেন "এক row-এর গুণিতক আরেকটায় যোগ" চালে সেই গুণিতকের সহগ \(c=0\) হলেও ক্ষতি নেই, কিন্তু scale-চালে \(c=0\) সর্বনাশা।

Solution

Swap: \(R_i \leftrightarrow R_j\)-এর উল্টো আবার \(R_i \leftrightarrow R_j\) — নিজেই নিজের ওষুধ, এবং অবশ্যই একটা ERO।
Scale: \(R_i \leftarrow cR_i\) (\(c\ne0\))-এর উল্টো \(R_i \leftarrow \frac1c R_i\) — \(\frac1c\) সংজ্ঞায়িত ও nonzero, তাই বৈধ ERO।
Add: \(R_i \leftarrow R_i + cR_j\)-এর উল্টো \(R_i \leftarrow R_i - cR_j\) — আবার একই ধরনের চাল।

Add-চালে \(c=0\) মানে "কিছুই কোরো না" — অকেজো কিন্তু নিরীহ; row-এর তথ্য অটুট। Scale-এ \(c=0\) মানে \(R_i\) পুরো মুছে \(0=0\) বসানো — একটা equation-এর তথ্য চিরতরে হারায়, উল্টো চাল অসম্ভব (\(\frac10\) নেই), তাই সমাধান সেট বদলে (বড় হয়ে) যেতে পারে। যেমন \(x=1, y=2\) সিস্টেমের দ্বিতীয় row-কে \(0\) দিয়ে গুণ করলে পাই "\(x=1\), \(0=0\)" — হঠাৎ অসীম সমাধান!

Problem 7. (কোডে ভাবো) তোমার বন্ধু rref লিখেছে, কিন্তু pivot বাছার সময় "প্রথম nonzero" নেয় এবং exact A[i,col] != 0 দিয়ে চেক করে। \(\begin{pmatrix}10^{-17}&1\\1&1\end{pmatrix}\mathbf{x}=\binom{1}{2}\) সিস্টেমে (আসল সমাধান \(x\approx1, y\approx1\)) তার কোড কী বিপদে পড়তে পারে?

Solution

দুটো বিপদ:

১) \(10^{-17}\) গাণিতিকভাবে nonzero, তাই != 0 পরীক্ষা তাকে pivot বানাবে। তারপর \(R_2 \leftarrow R_2 - 10^{17}R_1\) — বিশাল সংখ্যার সাথে ছোট সংখ্যার যোগবিয়োগে floating point-এ \(R_2\)-এর আসল তথ্য (সেই \(1\)-গুলো) rounding-এ ধুয়েমুছে যায়; উত্তর ভয়ানক ভুল আসতে পারে।

২) সংখ্যাটা যদি হতো কোনো আগের ধাপের ফল — গাণিতিকভাবে শূন্য হওয়ার কথা কিন্তু rounding-এ \(10^{-17}\) রয়ে গেছে — তাহলে সে একটা ভুতুড়ে pivot পেতো যেখানে আসলে free column হওয়ার কথা।

প্রতিকার: (i) partial pivoting — column-এর সবচেয়ে বড় মানের entry-কে swap করে pivot বানানো (তখন pivot হবে \(1\), নিরাপদ), (ii) np.isclose(A[i,col], 0)-জাতীয় tolerance দিয়ে শূন্য-পরীক্ষা। §৬-এর কোড দুটোই করে; গভীর বিশ্লেষণ Part VIII-এ।

৯. Common ভুল¶

ভুল ১: Row operation-টা \(\mathbf{b}\) column-এ প্রয়োগ করতে ভুলে যাওয়া। ✗ \(R_2 \leftarrow R_2 - 2R_1\) করলে দাগের ডানের entry-তেও করতে হবে! ✓ ঠিক অভ্যাস: augmented matrix-কে একটাই matrix ভাবো — চাল পুরো row জুড়ে, দাগ পেরিয়ে।

ভুল ২: Column operation করা। ✗ দুটো column অদলবদল বা যোগ করলে সমাধান সেট বদলে যায় (variable-দের নাম/অর্থ গুলিয়ে যায়)। ✓ Elimination-এ শুধু row operation — কারণ প্রতিটা row একটা equation, আর equation-দের নাড়াচাড়াই নিরাপদ।

ভুল ৩: RREF আর REF গুলিয়ে ফেলা। ✗ শুধু নিচের দিক শূন্য করে থেমে গেলে সেটা Row Echelon Form — pivot-এর উপরে তখনো ময়লা। ✓ RREF-এ pivot column-এ pivot ছাড়া সব শূন্য, আর প্রতিটা pivot ঠিক \(1\)। উত্তর সরাসরি পড়তে চাইলে RREF পর্যন্ত যাও।

ভুল ৪: "Free variable মানে variable-টা শূন্য" ভাবা। ✗ Free মানে "শূন্য" নয় — মানে স্বাধীন: যেকোনো মান নিতে পারে। ✓ Free variable-কে parameter (\(t, s\)) ধরে pivot variable-দের তার ভাষায় প্রকাশ করো (Example 2)।

ভুল ৫: দুটো চাল একসাথে করে গোঁজামিল। ✗ \(R_1 \leftarrow 2R_1 - 3R_2\) জাতীয় "কম্বো চাল" — এখানে \(R_1\)-কে scale-ও করা হচ্ছে; দুই ধাপ মিশে গিয়ে চিহ্নের ভুল হয় প্রায়ই (আর determinant-এর হিসাবেও পরে গোলমাল বাধায়)। ✓ প্রতি লাইনে একটা ERO; scale আর add আলাদা ধাপে। ধীর, কিন্তু নির্ভুল।

১০. এক নজরে¶

ধারণা	এক লাইনে
ERO (৩টা)	swap \(R_i\leftrightarrow R_j\); scale \(R_i\leftarrow cR_i\ (c\ne0)\); add \(R_i\leftarrow R_i+cR_j\)
কেন নিরাপদ	প্রতিটার উল্টো চাল আছে → সমাধান সেট অটুট
Gaussian elimination	forward pass (নিচে শূন্য, সিঁড়ি) + backward pass (উপরে শূন্য)
RREF-এর ৪ নিয়ম	pivot \(=1\); pivot column-এ একা; সিঁড়ি ডানে নামে; শূন্য row নিচে
RREF unique	পথ যা-ই হোক, গন্তব্য একটাই
রায় পড়া	\(0=1\) row → নেই; সব column-এ pivot → ১টা; free column → অসীম
Free variable	pivot-হীন column-এর variable; parameter হয়ে সমাধানে ঘোরে

পরের chapter-এর সেতু: এই chapter-এ চালগুলো করেছি "হাতে"। Chapter 2.3-এ দেখবে প্রতিটা ERO আসলে একটা ছোট্ট matrix দিয়ে গুণ করা — আর সেই দৃষ্টিতে elimination-এর পুরো খাতাটা গুছিয়ে রাখা যায় দুটো ত্রিভুজাকার matrix-এ: বিখ্যাত LU Decomposition, যেটা বাস্তবের সব বড় solver-এর ইঞ্জিন।

📓 Notebook Project¶

notebooks/part-02/ch02-project.ipynb — Part II-এর flagship project: নিজের হাতে একটা step-by-step Gaussian elimination visualizer বানাও — প্রতিটা row operation-এ augmented matrix-এর ছবি (heatmap) আঁকবে, pivot হাইলাইট করবে, আর শেষে সমাধান-রায় ঘোষণা করবে।