مثال ۲۱.۲: یافتن کوچکترین $k$ در لم وابستگی خطی

۱. متن مثال کتاب آکسلر

۲. پیاده‌سازی گام‌به‌گام الگوریتم آکسلر

گام اول: بررسی $k = 1$

• شرط نظری: $k = 1$ کار می‌کند اگر و تنها اگر $v_1 \in \operatorname{span}() = \{0\}$ باشد؛ یعنی اولین بردار، بردار صفر باشد.
• بررسی: $$v_1 = (1, 2, 3) \neq (0, 0, 0)$$
• نتیجه: $k = 1$ نیست.

گام دوم: بررسی $k = 2$

• شرط نظری: $k = 2$ کار می‌کند اگر و تنها اگر دومین بردار مضرب اسکالر اولین بردار باشد ($v_2 \in \operatorname{span}(v_1)$).
• بررسی: آیا اسکالر $c \in \mathbb{R}$ وجود دارد به طوری که $(6, 5, 4) = c(1, 2, 3)$؟
  • برای مولفه اول: $c = 6$
  • برای مولفه دوم: $5 \neq 6(2) = 12$
  • تناقض!
• نتیجه: دو بردار هم‌خط نیستند؛ پس $k = 2$ نیست.

گام سوم: بررسی $k = 3$

• شرط نظری: $k = 3$ کار می‌کند اگر و تنها اگر سومین بردار ترکیب خطی دو بردار اول باشد ($v_3 \in \operatorname{span}(v_1, v_2)$).
• بررسی: آیا اسکالرهایی مانند $a, b \in \mathbb{R}$ وجود دارند به طوری که: $$(15, 16, 17) = a(1, 2, 3) + b(6, 5, 4)$$
• این تساوی معادل دستگاه ۳ معادله و ۲ مجهول زیر است: a + 6b = 15 & (1) \\ 2a + 5b = 16 & (2) \\ 3a + 4b = 17 & (3) \end{cases}$$
• حل دستگاه: از معادله (۱) داریم $a = 15 - 6b$. جایگذاری در معادله (۲): $$2(15 - 6b) + 5b = 16 \implies 30 - 12b + 5b = 16 \implies -7b = -14 \implies b = 2$$ بنابراین: $$a = 15 - 6(2) = 15 - 12 = 3$$
• بررسی سازگاری با معادله (۳): $$3a + 4b = 3(3) + 4(2) = 9 + 8 = 17$$ معادله سوم کاملاً برقرار است!
• نتیجه: ضرایب $a = 3$ و $b = 2$ جواب یکتا هستند و بنابراین: $$(15, 16, 17) = 3(1, 2, 3) + 2(6, 5, 4) \in \operatorname{span}(v_1, v_2)$$ پس کوچک‌ترین مقدار $k$ برابر با ۳ است ($k = 3$).

۳. نتیجه‌گیری عملیاتی طبق لم وابستگی خطی

چون $k = 3$ شرط لم را برآورده می‌کند:

می‌توان بردار سوم یعنی $(15, 16, 17)$ را از لیست چهارعضوی حذف کرد بدون اینکه گستره کل تغییر کند:

$$\operatorname{span}\big((1, 2, 3), (6, 5, 4), (15, 16, 17), (8, 9, 7)\big) = \operatorname{span}\big((1, 2, 3), (6, 5, 4), (8, 9, 7)\big)$$

این تکنیک دقیقاً هسته اصلی الگوریتم تبدیل لیست مولد به پایه (قضیه ۳۰.۲) است.

۴. ارتباطات و پیوندهای اتمیک

• لم مرجع: لم ۱۹.۲: لم وابستگی خطی
• قضیه نامساوی طول: قضیه ۲۲.۲: طول لیست مستقل کمتر مساوی طول لیست مولد
• کاربرد در غربال کردن پایه‌ها: قضیه ۳۰.۲: کاهش هر لیست مولد به یک پایه