اساسی‌ترین نامساوی جبر خطی

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

$$\text{طول هر لیست مستقل خطی} \le \text{طول هر لیست گسترش‌دهنده}$$

این قضیه ضامن خوش‌تعریف بودن مفهوم «بُعد» در سراسر ریاضیات است.

قضیه ۲۲.۲ کتاب آکسلر

در یک فضای برداری با بعد متناهی، طول هر لیست مستقل خطی از بردارها کمتر یا مساوی طول هر لیست گسترش‌دهنده از بردارها است. به بیان صوری: اگر $u_1, \dots, u_m$ در $V$ مستقل خطی باشد، و $w_1, \dots, w_n$ فضا را گسترش دهد، آنگاه:

$$m \le n$$

اثبات شاهکار آکسلر

فرض کنید $u_1, \dots, u_m$ در $V$ مستقل خطی باشد و $w_1, \dots, w_n$ فضای $V$ را گسترش دهد. فرآیند را در $m$ مرحله دنبال می‌کنیم:

مرحله ۱: فرض کنید $B$ لیست اولیه $w_1, \dots, w_n$ باشد. افزودن $u_1$ در ابتدای این لیست، لیست جدید زیر را می‌سازد:

$$u_1, w_1, \dots, w_n$$

چون $w_1, \dots, w_n$ فضا را اسپن می‌کند، بردار $u_1 \in \operatorname{span}(w_1, \dots, w_n)$ است. بنابراین لیست فوق وابسته خطی است. طبق لم وابستگی خطی (۱۹.۲)، یکی از بردارها در این لیست، در گستره بردارهای قبلی قرار دارد:

• آیا بردار اول ($u_1$) می‌تواند باشد؟ خیر! زیرا $u_1 \in \operatorname{span}() = \{0\}$ به معنای $u_1 = 0$ است، در حالی که $u_1$ عضوی از یک لیست مستقل خطی است و قطعاً ناصفر است.
• بنابراین برداری که در گستره قبلی‌ها قرار دارد، لزوماً یکی از بردارهای $w$ است (مثلاً $w_j$). با حذف این $w_j$، طبق لم ۱۹.۲، لیست حاصل که طول آن هنوز $n$ است (شامل $u_1$ و $n-1$ بردار از $w$ها) همچنان $V$ را گسترش می‌دهد: $$B = u_1, w_1, \dots, \widehat{w_j}, \dots, w_n$$

مرحله $j$ (برای $j = 2, \dots, m$): فرض استقرا: در پایان مرحله $j-1$، لیستی به طول $n$ شامل:

$$u_1, \dots, u_{j-1}, \text{و } n - (j-1) \text{ بردار از } w\text{ها}$$

داریم که کل $V$ را گسترش می‌دهد. حال بردار $u_j$ را بعد از $u_{j-1}$ و قبل از $w$های باقی‌مانده وارد لیست می‌کنیم:

$$u_1, \dots, u_{j-1}, u_j, w_{i_1}, \dots, w_{i_p}$$

طول این لیست اکنون $n + 1$ است. چون لیست قبلی $V$ را گسترش می‌داد، $u_j$ در گستره آن قرار دارد و بنابراین این لیست $n+1$ عضوی وابسته خطی است. طبق لم وابستگی خطی (۱۹.۲)، عنصری در این لیست وجود دارد که در گستره بردارهای ماقبل خود است:

• آیا این عنصر می‌تواند یکی از بردارهای $u_1, \dots, u_j$ باشد؟ پاسخ قاطعانه خیر است! زیرا اگر $u_r \in \operatorname{span}(u_1, \dots, u_{r-1})$ با $r \le j$ باشد، طبق تعریف، لیست $u_1, \dots, u_j$ وابسته خطی می‌شد، که تناقض آشکار با فرض مستقل خطی بودن زیرلیست $u_1, \dots, u_m$ است!
• بنابراین عنصری که در گستره قبلی‌ها قرار گرفته، حتماً و حتماً یکی از $w$های باقی‌مانده است.
• این یعنی در این مرحله هنوز باید حداقل یک $w$ در لیست موجود باشد تا حذف شود. آن $w$ را حذف می‌کنیم؛ لیست جدید با طول $n$ شامل $u_1, \dots, u_j$ و بقیه $w$ها مجدداً کل $V$ را گسترش می‌دهد.

نتیجه‌گیری و بستن اثبات: این فرآیند جایگزینی را می‌توان تا مرحله $m$ ادامه داد. در هر مرحله دقیقاً یک بردار $w$ حذف شد. از آنجا که در هر یک از مراحل $1$ تا $m$ یک بردار از میان $w$ها خارج گردید و تعداد کل بردارهای اولیه $w$ برابر $n$ بود، غیرممکن است که تعداد مراحل ($m$) از تعداد بردارهای موجود ($n$) بیشتر باشد. اگر $m > n$ می‌بود، پس از مرحله $n$-ام تمام $w$ها تمام می‌شدند و لیست فقط شامل $u_1, \dots, u_n$ می‌شد که فضا را اسپن می‌کرد؛ آنگاه بردار بعدی $u_{n+1}$ ترکیب خطی از $u_1, \dots, u_n$ می‌شد که با استقلال خطی لیست $u$ تناقض دارد. بنابراین با قطعیت ریاضی:

$$m \le n \quad \blacksquare$$