Задача 11

Условие задачи

Любые $k$ столбцов матрицы $A$ линейно независимы. Докажите, что система $Ax = b$ не может иметь двух разных решений с числом ненулевых элементов меньше $\dfrac{k}{2}$.

Решение задачи

Введём понятие: $\operatorname{supp}(x)$ — это носитель вектора $x$, определяется как множество индексов ненулевых элементов вектора: $\operatorname{supp}(x) = \left\{i : x_i \ne 0\right\}$. Соответственно, через $\left|\operatorname{supp}(x)\right|$ записывается мощность такого множества.

Приступим непосредственно к решению.

Пусть, вопреки доказываемому, у системы $Ax = b$ есть два различных решения $x$ и $y$, причём

$$\left|\operatorname{supp}(x)\right| < \dfrac{k}{2}, \quad \left|\operatorname{supp}(y)\right| < \dfrac{k}{2} \ \text{.}$$

По §2.2 произведение матрицы на столбец коэффициентов есть линейная комбинация её столбцов, $Ax = \sum\limits_{j=1}^n x_j a_j$; поэтому равенство $Ax = b$ – это в точности $\sum\limits_{j=1}^n x_j a_j = b$. Выписав это для каждого из двух наших решений, получаем два равенства

$$\sum\limits_{j=1}^n x_j a_j = b, \quad \sum\limits_{j=1}^n y_j a_j = b \ \text{.} \tag{1}$$

Положим

$$z := x - y \ \text{.}$$

Так как решения различны, $x \ne y$, то $z \ne 0$; значит, у $z$ есть хотя бы один ненулевой элемент:

$$\left|\operatorname{supp}(z)\right| \geqslant 1 \ \text{.} \tag{2}$$

Составим линейную комбинацию столбцов с коэффициентами $z$ и распишем её поэлементно $z_j = x_j - y_j$, пользуясь лишь свойствами действий над арифметическими векторами: для каждого $j$ выполнено $\left(x_j - y_j\right) a_j = x_j a_j - y_j a_j$, а конечную сумму таких разностей можно перегруппировать в разность двух сумм. Обе получившиеся суммы уже вычислены в $\left(1\right)$ – каждая равна $b$:

$$\begin{gathered} \sum\limits_{j=1}^n z_j a_j = \sum\limits_{j=1}^n \left(x_j - y_j\right) a_j = \\ = \sum\limits_{j=1}^n x_j a_j - \sum\limits_{j=1}^n y_j a_j = \\ = b - b = 0 \ \text{.} \end{gathered} \tag{3}$$

Это и есть равенство $Az = 0$.

Покажем включение

$$\operatorname{supp}(z) \subseteq \operatorname{supp}(x) \cup \operatorname{supp}(y) \ \text{.}$$

Возьмём любой индекс $j \in \operatorname{supp}(z)$, то есть $z_j \ne 0$. По определению $z_j = x_j - y_j$, поэтому $x_j - y_j \ne 0$, а значит $x_j \ne y_j$. Но если бы было сразу $x_j = 0$ и $y_j = 0$, то $x_j = y_j$; следовательно, хотя бы одно из чисел $x_j, \, y_j$ отлично от нуля. В первом случае $j \in \operatorname{supp}(x)$, во втором $j \in \operatorname{supp}(y)$; в любом случае $j \in \operatorname{supp}(x) \cup \operatorname{supp}(y)$. Включение доказано.

Мощность объединения не превосходит суммы мощностей, поэтому

$$\left|\operatorname{supp}(z)\right| \leqslant \left|\operatorname{supp}(x) \cup \operatorname{supp}(y)\right| \leqslant \\ \leqslant \left|\operatorname{supp}(x)\right| + \left|\operatorname{supp}(y)\right| \ \text{.}$$

Оба слагаемых $\left|\operatorname{supp}(x)\right|, \, \left|\operatorname{supp}(y)\right|$ – целые неотрицательные числа, каждое меньше $\dfrac{k}{2}$. Сумма двух чисел, каждое из которых меньше $\dfrac{k}{2}$, есть целое число, меньшее $k$; будучи целым и меньшим $k$, оно не превосходит $k - 1$. Итак,

$$\left|\operatorname{supp}(z)\right| \leqslant \left|\operatorname{supp}(x)\right| + \left|\operatorname{supp}(y)\right| < \\ <\dfrac{k}{2} + \dfrac{k}{2} = k \Rightarrow \left|\operatorname{supp}(z)\right| \leqslant k - 1\ \text{.}$$

Обозначим для краткости $s := \left|\operatorname{supp}(z)\right|$. С учётом $\left(2\right)$ получаем

$$1 \leqslant s \leqslant k - 1 < k \ \text{.}$$

Пусть

$$\operatorname{supp}(z) = \left\{i_1, \, \ldots, \, i_s\right\}$$

– перечень индексов ненулевых элементов $z$ (по определению $z_{i_t} \ne 0$ при всех $t = 1, \, \ldots, \, s$). В сумме $\left(3\right)$ все слагаемые с индексами $j \notin \operatorname{supp}(z)$ имеют $z_j = 0$; остаются лишь слагаемые с $j \in \operatorname{supp}(z)$:

$$\sum\limits_{t=1}^s z_{i_t} a_{i_t} = 0 \ \text{.} \tag{4}$$

Итак, имеем $s$ различных столбцов $a_{i_1}, \, \ldots, \, a_{i_s}$ и, соответственно, $s$ различных индексов $i_1, \, \ldots, \, i_s$, причём $s < k$. Обозначим общее число столбцов матрицы $A$ за $n$, тогда из условия задачи $n \geqslant k$. Значит, среди оставшихся $n - s \geqslant k - s \geqslant 1$ индексов можно выбрать ещё $k - s$ различных и добавить их к нашим, получив ровно $k$ различных индексов

$$i_1, \, \ldots, \, i_s, \, i_{s+1}, \, \ldots, \, i_k \ \text{.}$$

По условию задачи любые $k$ столбцов независимы – в частности, независимы и эти $k$ столбцов $a_{i_1}, \, \ldots, \, a_{i_k}$.

Проверим независимость исходных $s$ столбцов (они теперь являются подсистемой для $a_{i_1}, \, \ldots, \, a_{i_k}$). Пусть некоторая их линейная комбинация равна нулю:

$$\sum\limits_{t=1}^s \lambda_t a_{i_t} = 0 \ \text{.}$$

Допишем к ней нулевые коэффициенты при добавленных столбцах, положив $\lambda_{s+1} = \ldots = \lambda_{k} = 0$. От этого сумма не изменится:

$$\sum\limits_{t=1}^k \lambda_t a_{i_t} = \sum\limits_{t=1}^s \lambda_t a_{i_t} + \sum\limits_{t=s+1}^k 0 \cdot a_{i_t} = 0 \ \text{.}$$

Слева – линейная комбинация всех $k$ независимых столбцов $a_{i_1}, \, \ldots, \, a_{i_k}$, равная нулю; по независимости все её коэффициенты нулевые:

$$\lambda_1 = \ldots = \lambda_s = \ldots = \lambda_k = 0 \ \text{.}$$

В частности $\lambda_1 = \ldots = \lambda_s = 0$. Значит, нулю может равняться лишь тривиальная комбинация столбцов $a_{i_1}, \, \ldots, \, a_{i_s}$ – они линейно независимы.

Равенство $\left(4\right)$ – это нулевая линейная комбинация независимых столбцов $a_{i_1}, \, \ldots, \, a_{i_s}$ с коэффициентами $z_{i_t}$. По независимости она обязана быть тривиальной:

$$z_{i_1} = \ldots = z_{i_s} = 0 \ \text{.}$$

Но индексы $i_1, \ldots, i_s$ выбирались ровно те, где $z_{i_t} \ne 0$. Получаем $z_{i_t} = 0$ и $z_{i_t} \ne 0$ одновременно – противоречие.

Предположение о существовании двух различных решений, у каждого из которых меньше $\dfrac{k}{2}$ ненулевых элементов, привело к противоречию. Следовательно, система $Ax = b$ не может иметь двух различных решений с числом ненулевых элементов меньше $\dfrac{k}{2}$. $\square$