رفتن به متن
باغ ریاضی
قضیه ۲۹.۲ هر لیست مولد شامل یک پایه است (کاهش به پایه)
تنظیمات مطالعه
تنظیمات مطالعه

قضیه ۲۹.۲ هر لیست مولد شامل یک پایه است (کاهش به پایه)

#قضیه#اثبات#الگوریتم#پایه#کاهش_پایه#لم_وابستگی_خطی#فصل_۲#جبر_خطی#آکسلر#تجسم_هندسی#جئوجبرانسخهٔ رسمی

یادداشت شما ذخیره شد

می‌خواهید این تغییرات برای مدیر وب‌سایت هم ارسال شوند؟ نسخهٔ رسمی تنها پس از تأیید تغییر می‌کند.

قضیه ۲۹.۲: هر لیست مولد شامل یک پایه است (کاهش به پایه)

پیام کلیدی قضیه در یک جمله

از هر فهرست مولد در یک فضای برداری می‌توان بردارهای اضافه و هرز را با یک الگوریتم گام‌به‌گام (غربال) دور ریخت تا به یک پایه خالص و بهینه رسید.

۱. تصویر کلان و الگوریتم غربال (The Sieve Process)

اگر یک گونی پر از سنگ و گوهر داشته باشید که نیاز شما را کاملاً برطرف می‌کند (فضا را گسترش می‌دهد)، چگونه اشیاء تکراری و بی‌ارزش را حذف می‌کنید؟ از اولین شیء شروع می‌کنید؛ اگر پوچ بود دور می‌اندازید. سپس هر شیء جدید را نگاه می‌کنید: اگر با اشیاء قبلی که نگه داشته‌اید قابل ساختن بود، زائد است و آن را دور می‌اندازید. این فرآیند زیبا و الگوریتمی دقیقاً همان چیزی است که آکسلر برای استخراج یک پایه از هر لیست مولد به کار می‌برد.

۲. صورت دقیق ریاضی قضیه

قضیه ۳۰.۲ کتاب آکسلر (کاهش به پایه)

هر فهرست گسترش‌دهنده (مولد) در یک فضای برداری را می‌توان با حذف برخی (احتمالاً هیچ‌کدام) از بردارها، به یک پایه از آن فضای برداری کاهش داد.

۳. نقشه راه و الگوریتم اثبات (Proof Algorithm)

  • نوع اثبات: اثبات ساختاری و الگوریتمی با استفاده از لم وابستگی خطی ۱۹.۲.
  • مراحل الگوریتم:
    • لیست B=(v1,…,vn)B = (v_1, \dots, v_n) را قرار می‌دهیم.
    • مرحله ۱: اگر v1=0v_1 = \mathbf{0} بود، آن را از BB حذف می‌کنیم؛ وگرنه دست‌نخورده می‌ماند.
    • مرحله kkام: اگر vk∈span⁡(v1,…,vk−1)v_k \in \operatorname{span}(v_1, \dots, v_{k-1}) بود، vkv_k را حذف می‌کنیم؛ در غیر این صورت آن را حفظ می‌کنیم.
    • پس از nn مرحله، خروجی BB یک پایه خواهد بود.

۴. اثبات دقیق گام‌به‌گام (Step-by-Step Proof)

اثبات رسمی قضیه کاهش به پایه

فرض کنید فهرست (v1,…,vn)(v_1, \dots, v_n) فضای برداری VV را گسترش دهد:

span⁡(v1,…,vn)=V\operatorname{span}(v_1, \dots, v_n) = V

فرآیند چندمرحله‌ای زیر را برای غربال کردن بردارها اجرا می‌کنیم. با B=(v1,…,vn)B = (v_1, \dots, v_n) شروع کنید:

مرحله ۱: اگر v1=0v_1 = \mathbf{0}، بردار v1v_1 را از BB حذف کنید. اگر v1≠0v_1 \neq \mathbf{0}، فهرست BB را بدون تغییر بگذارید.

مرحله kk (برای k=2,…,nk = 2, \dots, n): اگر vkv_k در گستره بردارهای پیشین خود باشد، یعنی:

vk∈span⁡(v1,…,vk−1)v_k \in \operatorname{span}(v_1, \dots, v_{k-1})

آنگاه vkv_k را از فهرست BB حذف کنید. اگر vk∉span⁡(v1,…,vk−1)v_k \notin \operatorname{span}(v_1, \dots, v_{k-1})، فهرست BB را بدون تغییر نگه دارید.

پس از اجرای مرحله nnام توقف کنید. فهرست نهایی را BB می‌نامیم.

گام اول: اثبات مولد بودن فهرست نهایی BB فهرست اولیه (v1,…,vn)(v_1, \dots, v_n) کل VV را گسترش می‌داد. در طول الگوریتم، ما تنها بردارهایی مانند vkv_k را حذف کردیم که خود در گستره بردارهای قبلی قرار داشتند. طبق بخش (b) از لم وابستگی خطی ۱۹.۲، حذف برداری که در اسپن بردارهای ماقبل خود است، هیچ تغییری در گستره کل فهرست ایجاد نمی‌کند:

span⁡(B)=span⁡(v1,…,vn)=V\operatorname{span}(B) = \operatorname{span}(v_1, \dots, v_n) = V

بنابراین فهرست BB همچنان کل فضا را گسترش می‌دهد.

گام دوم: اثبات استقلال خطی فهرست نهایی BB الگوریتم ساختاری ما تضمین می‌کند که هیچ برداری در BB در گستره بردارهای قبلی خود در BB قرار ندارد (چون هر برداری که این خاصیت را داشت در همان مرحله غربال شد و حذف گردید، و بردار صفر نیز در مرحله ۱ حذف شد). طبق بخش (a) از لم وابستگی خطی ۱۹.۲، اگر فهرستی وابسته خطی باشد، حتماً عضوی در آن وجود دارد که در اسپن بردارهای قبلی است. چون در فهرست BB چنین عضوی وجود ندارد، پس BB نمی‌تواند وابسته خطی باشد. بنابراین BB مستقل خطی است.

نتیجه نهایی: چون BB هم VV را گسترش می‌دهد و هم مستقل خطی است، طبق تعریف ۲۶.۲، BB یک پایه برای VV است. ■\blacksquare

۵. مثال عملی از اجرای الگوریتم

فرض کنید در فضای R2\mathbb{R}^2 فهرست مولد زیر را داریم:

((1,2),(3,6),(4,7),(5,9))((1, 2), (3, 6), (4, 7), (5, 9))

الگوریتم را گام‌به‌گام پیاده می‌کنیم:

  • مرحله ۱: بردار اول v1=(1,2)≠(0,0)v_1 = (1, 2) \neq (0, 0) است.   ⟹  \implies نگه می‌داریم. لیست فعلی: ((1,2))((1, 2)).
  • مرحله ۲: بردار دوم v2=(3,6)=3(1,2)∈span⁡(v1)v_2 = (3, 6) = 3(1, 2) \in \operatorname{span}(v_1) است.   ⟹  \implies حذف می‌کنیم. لیست فعلی: ((1,2))((1, 2)).
  • مرحله ۳: بردار سوم v3=(4,7)v_3 = (4, 7) در اسپن (1,2)(1, 2) نیست (مضرب آن نیست).   ⟹  \implies نگه می‌داریم. لیست فعلی: ((1,2),(4,7))((1, 2), (4, 7)).
  • مرحله ۴: بردار چهارم v4=(5,9)v_4 = (5, 9) است. چون دو بردار قبلی کل R2\mathbb{R}^2 را اسپن می‌کنند، v4v_4 قطعاً در اسپن آنهاست.   ⟹  \implies حذف می‌کنیم.
  • خروجی نهایی: فهرست ((1,2),(4,7))((1, 2), (4, 7)) که یک پایه خالص برای R2\mathbb{R}^2 است.
کاهش لیست مولد به پایه: v2 روی خط v1 است و حذف می‌شود؛ v4 ترکیب خطی v1 و v3 است و حذف می‌شود، و تنها {v1, v3} به عنوان پایه باقی می‌مانند
  • v1 و v2 هم‌راستا هستند (v2 = 3*v1)؛ بنابراین v2 زائد است و حذف می‌شود.
  • v3 در راستای متفاوتی است و کل صفحه R2 توسط v1 و v3 اسپن می‌شود.
  • v4 در گستره دو بردار قبلی قرار می‌گیرد و به عنوان بردار اضافه غربال می‌شود.
کد اصلی رسم
appName: classic
width: 650
height: 380
showToolBar: false
showAlgebraInput: true
showMenuBar: false
commands:
  - "O = (0, 0)"
  - "Pt1 = (1, 2)"
  - "v1 = Vector(O, Pt1)"
  - "Pt2 = (3, 6)"
  - "v2 = Vector(O, Pt2)"
  - "Pt3 = (4, 7)"
  - "v3 = Vector(O, Pt3)"
  - "Pt4 = (5, 9)"
  - "v4 = Vector(O, Pt4)"
  - "Pt5 = (1, 2)"
  - "line1 = Line(O, Pt5)"
caption: "کاهش لیست مولد به پایه: v2 روی خط v1 است و حذف می‌شود؛ v4 ترکیب خطی v1 و v3 است و حذف می‌شود، و تنها {v1, v3} به عنوان پایه باقی می‌مانند"
explain:
  - "v1 و v2 هم‌راستا هستند (v2 = 3*v1)؛ بنابراین v2 زائد است و حذف می‌شود."
  - "v3 در راستای متفاوتی است و کل صفحه R2 توسط v1 و v3 اسپن می‌شود."
  - "v4 در گستره دو بردار قبلی قرار می‌گیرد و به عنوان بردار اضافه غربال می‌شود."

۶. نکات کلیدی و هشدارهای امتحانی

نکات باریک‌تر از مو

  • وابستگی به ترتیب: نتیجه پایه به دست آمده بستگی به ترتیب اولیه بردارها دارد. اگر بردارها را جابه‌جا کنید، پایه‌ای متفاوت (اما با همان تعداد عضو) به دست خواهد آمد.
  • پایه حداقلی است: این قضیه اثبات می‌کند هر مجموعه مولد، درون خود یک اسکلت بنیادین (پایه) دارد و تمام شاخ و برگ‌های اضافی را می‌توان هرس کرد.

۷. پیوندها و گام‌های بعدی

پیوندهای این یادداشت ۳

یادداشت‌هایی که از این صفحه به آن‌ها پیوند داده شده است.

  • لم ۱۹.۲ لم وابستگی خطی (Linear Dependence Lemma)
    پیش‌نمایش

    لم ۱۹.۲: لم وابستگی خطی (Linear Dependence Lemma)

    قلب تپنده کتاب شلدون آکسلر

    اگر یک لیست از بردارها وابسته خطی باشد، آنگاه حداقل یکی از بردارها وجود دارد که در «گستره بردارهای پیش از خود» قرار گرفته است؛ و مهم‌تر اینکه، می‌توان این بردار زاید را از لیست حذف کرد بدون اینکه ذره‌ای از گستره (Span) کل لیست کاسته شود!

  • قضیه ۳۰.۲ هر فضای بعد متناهی دارای پایه است
    پیش‌نمایش

    قضیه ۳۰.۲: هر فضای بعد متناهی دارای پایه است

    پیام کلیدی قضیه در یک جمله

    وجود پایه در هیچ فضای بعد متناهی یک آرزو یا حدس نیست؛ قضیه وجود پایه تضمین می‌کند که هر فضای برداری با بعد متناهی دست‌کم یک پایه دارد.

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

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

    پیام کلیدی قضیه در یک جمله

    هر مجموعه از بردارهای مستقل خطی، هر چند کوچک، می‌تواند با افزودن بردارهای مناسب تکمیل شود و یک پایه کامل برای کل فضا تشکیل دهد؛ استقلال هیچ‌گاه بن‌بست نیست.

ارجاعات به این یادداشت ۱۲

یادداشت‌هایی که به این صفحه پیوند داده‌اند.

نمایش ۷ مورد دیگرنمایش کمتر

حالت ارائه