صورت دقیق مسئله (کتاب آکسلر، لم ۱۹.۲ و کاربردهای آن در بخش ۱.۲)

بخش الف (بیان و اثبات قضیه بنیادی): لم وابستگی خطی (Linear Dependence Lemma) را با دقت ریاضی بیان کنید و نشان دهید که اگر یک لیست $v_1, \dots, v_m$ از بردارها در $V$ وابسته خطی باشد، آنگاه اندیسی مانند $j \in \{1, \dots, m\}$ وجود دارد که:

1. $v_j \in \operatorname{span}(v_1, \dots, v_{j-1})$ (اگر $j=1$ باشد، یعنی $v_1 = 0$).
2. با حذف بردار $v_j$ از این لیست، گستره بردارهای باقیمانده دقیقاً برابر با گستره لیست اولیه خواهد بود.

بخش ب (مسئله تشریحی آزمون): لیست ۵ برداری زیر را در $\mathbb{R}^4$ در نظر بگیرید:

$$v_1 = (1, 2, 0, 1), \; v_2 = (2, 4, 0, 2), \; v_3 = (0, 1, 1, 0), \; v_4 = (1, 3, 1, 1), \; v_5 = (0, 0, 1, 0)$$

با پیاده‌سازی الگوریتم لم وابستگی خطی:

1. اولین بردار زائد را که در گستره بردارهای ماقبل خود قرار دارد، بیابید و آن را حذف کنید.
2. آیا لیست حاصل هنوز وابسته خطی است؟ بردار زائد بعدی را بیابید.
3. در نهایت یک زیرلیست مستقل خطی که همان گستره اولیه را دارد، استخراج نمایید.

اثبات تئوری و اجرای الگوریتم غربالگری

بخش الف: اثبات لم وابستگی خطی (قضیه ۱۹.۲ آکسلر)

گام اول: استفاده از فرض وابستگی خطی فرض کنید لیست $v_1, \dots, v_m$ وابسته خطی باشد. طبق تعریف، اسکالرهای $a_1, \dots, a_m \in \mathbb{F}$ وجود دارند که همگی صفر نیستند و:

$$a_1 v_1 + a_2 v_2 + \dots + a_m v_m = 0 \quad \text{--- (۱)}$$

گام دوم: انتخاب اندیس طلایی $j$ مجموعه اندیس‌هایی را که ضریب ناصفر دارند در نظر می‌گیریم: $\{ i \in \{1, \dots, m\} : a_i \neq 0 \}$. چون ضرایب همگی صفر نیستند، این مجموعه ناتهی است و دارای یک بزرگ‌ترین عضو است. فرض کنید:

$$j = \max \big\{ i \in \{1, \dots, m\} : a_i \neq 0 \big\}$$

این بدان معناست که:

• $a_j \neq 0$
• برای هر $k > j$، $a_k = 0$

گام سوم: اثبات شرط ۱ ($v_j \in \operatorname{span}(v_1, \dots, v_{j-1})$) اگر $j = 1$ باشد، معادله (۱) به صورت $a_1 v_1 = 0$ درمی‌آید. چون $a_1 \neq 0$، پس $v_1 = 0$ است و شرط اول برقرار است. اگر $j > 1$ باشد، معادله (۱) با توجه به صفر بودن جملات با اندیس بزرگتر از $j$ به شکل زیر نوشته می‌شود:

$$a_1 v_1 + \dots + a_{j-1} v_{j-1} + a_j v_j = 0$$

جمله $a_j v_j$ را در یک سمت نگه داشته و سایر جملات را به سمت راست منتقل می‌کنیم:

$$a_j v_j = -a_1 v_1 - \dots - a_{j-1} v_{j-1}$$

چون $a_j \neq 0$، طرفین را در $a_j^{-1}$ ضرب می‌کنیم:

$$v_j = -\frac{a_1}{a_j} v_1 - \dots - \frac{a_{j-1}}{a_j} v_{j-1}$$

این نمایش دقیقاً ثابت می‌کند که:

$$v_j \in \operatorname{span}(v_1, \dots, v_{j-1}) \quad \checkmark$$

گام چهارم: اثبات شرط ۲ (تساوی گستره پس از حذف $v_j$) فرض کنید $u \in \operatorname{span}(v_1, \dots, v_m)$ یک بردار دلخواه باشد. پس اسکالرهای $c_1, \dots, c_m$ وجود دارند به طوری که:

$$u = c_1 v_1 + \dots + c_{j-1} v_{j-1} + c_j v_j + c_{j+1} v_{j+1} + \dots + c_m v_m$$

اما دیدیم که $v_j$ ترکیبی خطی از $v_1, \dots, v_{j-1}$ است:

$$v_j = d_1 v_1 + \dots + d_{j-1} v_{j-1} \quad \Big(d_k = -\frac{a_k}{a_j}\Big)$$

این عبارت را به جای $v_j$ در فرمول $u$ قرار می‌دهیم:

$$u = c_1 v_1 + \dots + c_j (d_1 v_1 + \dots + d_{j-1} v_{j-1}) + \dots + c_m v_m$$

با فاکتورگیری از بردارهای باقیمانده، $u$ به عنوان ترکیبی خطی از لیست بدون $v_j$ نوشته می‌شود:

$$u \in \operatorname{span}(v_1, \dots, v_{j-1}, v_{j+1}, \dots, v_m)$$

بنابراین گستره با حذف $v_j$ دچار هیچ نقصی نخواهد شد. $\blacksquare$

---

بخش ب: حل عددی گام‌به‌گام برای بردارهای داده‌شده در $\mathbb{R}^4$

بردارها عبارتند از:

$$v_1 = (1, 2, 0, 1), \quad v_2 = (2, 4, 0, 2), \quad v_3 = (0, 1, 1, 0), \quad v_4 = (1, 3, 1, 1), \quad v_5 = (0, 0, 1, 0)$$

مرحله ۱ (بررسی $v_1$): $v_1 \neq (0, 0, 0, 0)$، بنابراین به عنوان عضو اول نگه داشته می‌شود.

مرحله ۲ (بررسی $v_2$): آیا $v_2 \in \operatorname{span}(v_1)$؟ به وضوح دیده می‌شود:

$$v_2 = (2, 4, 0, 2) = 2(1, 2, 0, 1) = 2v_1$$

بنابراین برای اندیس $j = 2$ داریم: $v_2 \in \operatorname{span}(v_1)$. طبق لم وابستگی خطی، $v_2$ بردار زائد اول است و حذف می‌شود. لیست جدید: $(v_1, v_3, v_4, v_5)$.

مرحله ۳ (بررسی $v_3$): آیا $v_3 \in \operatorname{span}(v_1)$؟ اگر $v_3 = c v_1$ باشد: $(0, 1, 1, 0) = c(1, 2, 0, 1) \implies c \cdot 1 = 0 \implies c = 0$. اما اگر $c=0$ باشد، $0 \cdot v_1 = (0,0,0,0) \neq v_3$. پس $v_3 \notin \operatorname{span}(v_1)$. بنابراین $v_3$ نگه داشته می‌شود. تا اینجا لیست مستقل ما $(v_1, v_3)$ است.

مرحله ۴ (بررسی $v_4$): آیا $v_4 \in \operatorname{span}(v_1, v_3)$؟ دستگاه معادله $v_4 = c_1 v_1 + c_3 v_3$ را تشکیل می‌دهیم:

$$(1, 3, 1, 1) = c_1 (1, 2, 0, 1) + c_3 (0, 1, 1, 0) = (c_1, \, 2c_1 + c_3, \, c_3, \, c_1)$$

با مقایسه مؤلفه‌ها:

• مؤلفه اول: $c_1 = 1$
• مؤلفه سوم: $c_3 = 1$
• مؤلفه چهارم: $c_1 = 1$ حال این مقادیر را در مؤلفه دوم چک می‌کنیم: $$2c_1 + c_3 = 2(1) + 1 = 3$$ که دقیقاً برابر با مؤلفه دوم $v_4$ است! بنابراین: $$v_4 = v_1 + v_3 \in \operatorname{span}(v_1, v_3)$$ طبق لم وابستگی خطی، $v_4$ بردار زائد دوم است و حذف می‌شود. لیست باقیمانده: $(v_1, v_3, v_5)$.

مرحله ۵ (بررسی $v_5$): آیا $v_5 \in \operatorname{span}(v_1, v_3)$؟ قرار می‌دهیم $v_5 = a v_1 + b v_3$:

$$(0, 0, 1, 0) = (a, \, 2a + b, \, b, \, a)$$

از مؤلفه اول و چهارم: $a = 0$. از مؤلفه دوم با فرض $a=0$: $2(0) + b = 0 \implies b = 0$. اگر $a=b=0$ باشد، مؤلفه سوم صفر می‌شود که با $1$ تناقض دارد. بنابراین $v_5 \notin \operatorname{span}(v_1, v_3)$ و $v_5$ باید نگه داشته شود.

نتیجه نهایی الگوریتم: زیرلیست مستقل خطی نهایی که دقیقاً همان گستره اولیه را دارد عبارت است از:

$$\big( v_1, v_3, v_5 \big) = \big( (1, 2, 0, 1), \; (0, 1, 1, 0), \; (0, 0, 1, 0) \big)$$

و بعد گستره اولیه برابر با ۳ است. $\blacksquare$

هشدارهای مهم در پیاده‌سازی لم وابستگی خطی

1. اشتباه در جهت زمان/اندیس: هرگز یک بردار را به وسیله بردارهای بعد از خودش حذف نکنید! لم وابستگی خطی تأکید می‌کند که $v_j$ باید در گستره $v_1, \dots, v_{j-1}$ باشد. رعایت این ترتیب برای الگوریتم استخراج پایه ضروری است.
2. حذف همزمان چند بردار وابسته: اگر متوجه شدید که $v_2$ وابسته به $v_1$ است و $v_4$ نیز وابسته به مجموع دیگر بردارهاست، نباید هر دو را کورکورانه در یک مرحله پاک کنید! هر بردار باید پس از حذف بردار زائد قبلی مورد ارزیابی قرار گیرد، زیرا ممکن است با حذف یکی، روابط وابستگی تغییر کند.
3. انتخاب بزرگ‌ترین اندیس: در اثبات تئوری، اگر فراموش کنید قید «بزرگ‌ترین اندیس با ضریب ناصفر» را ذکر کنید، نمی‌توانید تضمین کنید که ضرایب بعد از $j$ همگی صفر هستند و اثبات ناقص می‌ماند.