Разделы 
Дополнительно
Задача по математике - 756
2014-02-26 
Пусть заданы #T \in \mathbf{R}^{m \times n}# - матрица ранга #m,# #b \in \mathbf{R}^{m}# и множество #A = {x \in \mathbf{R}^{n} | Tx = b; x_{k} \geq 0, 1 \leq k \leq n}.# Доказать, что если точка #x \in A# является вершиной множества #A,# то существует такая нумерация #{i_{k}}_{k=1}^{n}# компонент точки #x,# что #x_{ik} = 0# Для всех #k \in \overline{m + 1, n},# а столбцы #{T_{ik}}_{k=1}^{m}# линейно независимы.
Решение:
Пусть #x# - вершина #A.# Если #x = 0,# то взяв #m# линейно независимых столбцов матрицы #T# (ранг #T# равен #m#) в качестве #T_{1}, \cdots, T_{m},# получаем требуемое условие. Пусть #x \in A \backslash \{ 0 \}# - вершина. Ясно, что можно так занумеровать компоненты #x,# что #x_{1} > 0, \cdots, x_{r} > 0,# а #x_{k} = 0# при #r + 1 \leq k \leq n.# Покажем, что в сумме #Tx = \sum_{k=1}^{r}T_{k}x_{k} + \sum_{k=r+1}^{n}T_{k}x_{k}# столбцы #\{ T_{k} \}_{k=1}^{r}# линейно независимы. Это завершит доказательство. Допустим, #\{ T_{k} \}_{k=1}^{r}# линейно зависимы, тогда найдется вектор #a \in \mathbf{R}^{n} : a = (\alpha_{1}, \cdots, \alpha_{r}, 0, \cdots, 0) \neq 0,# такой, что #\sum_{k=1}^{r}T_{k} \alpha_{k} =0.# Выберем #\varepsilon > 0# так, чтобы для любого #k# от 1 до #r# выполнялись неравенства #x_{k} \pm \varepsilon \alpha_{k} \geq 0.# Имеем #T(x \pm \varepsilon a) = \sum_{k=1}^{r}T_{k}(x_{k} \pm \varepsilon \alpha_{k}) + \sum_{k=r+1}^{r}T_{k}x_{k} = \sum_{k=1}^{r}T_{k}x_{k} \pm \varepsilon \sum_{k=1}^{r}T_{k}\alpha_{k} = b,# следовательно, #[x - \varepsilon a, x + \varepsilon a] \subset A# и, значит, #x# не является вершиной. Противоречие.
Пусть заданы #T \in \mathbf{R}^{m \times n}# - матрица ранга #m,# #b \in \mathbf{R}^{m}# и множество #A = {x \in \mathbf{R}^{n} | Tx = b; x_{k} \geq 0, 1 \leq k \leq n}.# Доказать, что если точка #x \in A# является вершиной множества #A,# то существует такая нумерация #{i_{k}}_{k=1}^{n}# компонент точки #x,# что #x_{ik} = 0# Для всех #k \in \overline{m + 1, n},# а столбцы #{T_{ik}}_{k=1}^{m}# линейно независимы.
Решение:
Пусть #x# - вершина #A.# Если #x = 0,# то взяв #m# линейно независимых столбцов матрицы #T# (ранг #T# равен #m#) в качестве #T_{1}, \cdots, T_{m},# получаем требуемое условие. Пусть #x \in A \backslash \{ 0 \}# - вершина. Ясно, что можно так занумеровать компоненты #x,# что #x_{1} > 0, \cdots, x_{r} > 0,# а #x_{k} = 0# при #r + 1 \leq k \leq n.# Покажем, что в сумме #Tx = \sum_{k=1}^{r}T_{k}x_{k} + \sum_{k=r+1}^{n}T_{k}x_{k}# столбцы #\{ T_{k} \}_{k=1}^{r}# линейно независимы. Это завершит доказательство. Допустим, #\{ T_{k} \}_{k=1}^{r}# линейно зависимы, тогда найдется вектор #a \in \mathbf{R}^{n} : a = (\alpha_{1}, \cdots, \alpha_{r}, 0, \cdots, 0) \neq 0,# такой, что #\sum_{k=1}^{r}T_{k} \alpha_{k} =0.# Выберем #\varepsilon > 0# так, чтобы для любого #k# от 1 до #r# выполнялись неравенства #x_{k} \pm \varepsilon \alpha_{k} \geq 0.# Имеем #T(x \pm \varepsilon a) = \sum_{k=1}^{r}T_{k}(x_{k} \pm \varepsilon \alpha_{k}) + \sum_{k=r+1}^{r}T_{k}x_{k} = \sum_{k=1}^{r}T_{k}x_{k} \pm \varepsilon \sum_{k=1}^{r}T_{k}\alpha_{k} = b,# следовательно, #[x - \varepsilon a, x + \varepsilon a] \subset A# и, значит, #x# не является вершиной. Противоречие.
