Задача 11

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

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

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

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

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

Пусть $x^{\left(1\right)}$ и $x^{\left(2\right)}$ – решения системы $Ax = b$, причём каждое из них имеет менее $\dfrac{k}{2}$ ненулевых элементов.

Предположим, что $x^{\left(1\right)} \ne x^{\left(2\right)}$.

Рассмотрим вектор $z = x^{\left(1\right)} - x^{\left(2\right)}$. Тогда $Az = Ax^{\left(1\right)} - Ax^{\left(2\right)} = b - b = 0$.

Кроме того, $\operatorname{supp}\left(z\right) \subseteq \operatorname{supp}\left(x^{\left(1\right)}\right) \cup \operatorname{supp} \left(x^{\left(2\right)}\right)$, поэтому $\left|\operatorname{supp}\left(z\right)\right| \leqslant \left|\operatorname{supp}\left(x^{\left(1\right)}\right)\right| + \left|\operatorname{supp}\left(x^{\left(2\right)}\right)\right| < \dfrac{k}{2} + \dfrac{k}{2} = k$.

Обозначим через $i_1, \, \ldots, \, i_s$ индексы ненулевых элементов вектора $z$. Тогда $s < k$, и из равенства $Az = 0$ получаем $z_{i_1} a_{i_1} + \ldots + z_{i_s} a_{i_s} = 0$, где $a_j$ – $j$-й столбец матрицы $A$.

Покажем, что столбцы $a_{i_1}, \, \ldots, \, a_{i_s}$ линейно независимы.

Действительно, если бы они были линейно зависимы, то любой набор из $k$ столбцов матрицы $A$, содержащий их, также был бы линейно зависим, что противоречит условию задачи.

Следовательно, столбцы $a_{i_1}, \, \ldots, \, a_{i_s}$ линейно независимы. Поэтому из равенства $z_{i_1} a_{i_1} + \ldots + z_{i_s} a_{i_s} = 0$ следует $z_{i_1} = \ldots = z_{i_s} = 0$.

Это противоречит выбору индексов $i_1, \, \ldots, \, i_s$, поскольку они соответствуют ненулевым элементам вектора $z$.

Следовательно, $z = 0$, то есть $x^{\left(1\right)} = x^{\left(2\right)}$.

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