экстремальные точки множества

[Anya90]

Помогите, пожалуйста, разобраться с доказательством.

Даны два множества:

$X=\{(x_1, x_2, ..., x_n)\in R^n, x_j\geq 0, j=1, 2, ..., n, \sum_{j=1}^n{x_j}\leq K\}$;

$Y=\{y\in R^n, y=Ax, x \in X\}$,

здесь $A$ - $m \times n$ матрица.

Нужно доказать, что если $y$ - экстремальная точка $Y$, то $y=Ax$, где $x$ - экстремальная точка $X$.

Рассуждения: предположим противное, т.е.
$y$ - экстремальная точка $Y$, $y=Ax$, но здесь $x$ не является экстремальной точкой $X$.
Это означает, что существуют точки $x_1, x_2, x_1 \neq x_2, x_1 \neq x, x_2 \neq x: x=x_1/2 + x_2/2$.
Умножив это равенство слева на матрицу А, получим
$Ax=Ax_1/2+Ax_2/2$ или $y=y_1/2+y_2/2$, что противоречит тому что $y$ - экстремальная точка.

В этом доказательстве мне непонятно, как мы можем знать, что $Ax_1\neq Ax_2$. Кто-нибудь может помочь? Спасибо.

[Alexey1]

Вектор $y \in \mathbb R^m$. А есть какие-нибудь ограничения на ранг матрицы $A$?

[Anya90]

Я думаю, что в этом случае матрица $A$ имеет линейно-независимые столбцы. Только не знаю, как это строго доказать.

[Circiter]

2Alexey1

Цитата:

Вектор $y\in\mathbb{R}^m$

Из условия ясно следует, что $A$ -- квадратная.

2Anya90

Цитата:

В этом доказательстве мне непонятно, как мы можем знать, что $Ax_1\neq Ax_2$

Допустим $Ax_1=Ax_2$. Если умножить обе части на $A^{-1}$, то получится $x_1=x_2$, опаньки. :) Ну это на случай если $A$ -- обратимая.

[Alexey1]

Circiter в сообщении #351945 писал(а):

Из условия ясно следует, что $A$ -- квадратная.

Откуда это следует? В условии написано $A$ это матрица $m \times n$.

Anya90 в сообщении #351908 писал(а):

Я думаю, что в этом случае матрица $A$ имеет линейно-независимые столбцы. Только не знаю, как это строго доказать.

Что значит доказать? Вы условия подгоняйте под доказательство?

[Circiter]

Alexey1 писал(а):

Откуда это следует?

Ну там же написано $y\in R^{\color{blue}n}$

[Alexey1]

Circiter в сообщении #351964 писал(а):

Ну там же написано $y\in R^{\color{blue}n}$

А дальше что там написано?

[Circiter]

2Alexey1
Опечатка получается? :)

2Anya90
А там точно в условии $\leqslant K$, а не наоборот? :)

[Circiter]

Ах, да, это я глупость ляпнул. :)

[Anya90]

Да, я опечаталась. $y \in R^m$.

Мне непонятно, как доказать, что матрица$A$ обратима. Хватает ли данных условий, чтобы это утверждать?
Натолкните, пожалуйста, на мысль.

[Alexey1]

Если Вам нужно условие при котором матрица $A$ обратима, то это условие: $A$ квадратная матрица с линейно независимыми столбцами.

[Anya90]

Хорошо. Это не мой случай. Она прямоугольная.

Вариант, предложенный выше, не подходит. Не объясните ли Вы поподробнее, что подразумевалось, когда Вы спрашивали про ранг. Если ранг полный, то столбцы будут л.нез., но как узнать, полный ли он?

[Alexey1]

Если столбцы линейно независимы, то $Ax=\sum\limits_{i=1}^{n}A_ix_i$, где $A_i$ столбцы матрицы $A$, то есть это просто линейная комбинация столбцов. При этих условиях, $Ax_1-Ax_2=A(x_1-x_2)=0$ только в том случае, если $x_1=x_2$, так как столбцы являются линейно независимыми.

[paha]

А что такое экстремальная точка? не лежащая во внутренности отрезка?

[Alexey1]

paha в сообщении #352264 писал(а):

А что такое экстремальная точка? не лежащая во внутренности отрезка?

Эта точка множества которая не может быть представлена как линейная комбинация двух других точек множества, то есть $x$ - экстремальная точка $X$, если $\not{\exists} z,y \in X, \ \not \exists \lambda \in (0,1), \ x = \lambda z+(1-\lambda)y$.