Седловой элемент матрицы

Седловой элемент матрицы $A=(a_{i,j}{)}_{i=1,j=1}^{m,n}$$A=(a_{{i,j}})_{{i=1,j=1}}^{{m,n}}$ — элемент матрицы $a_{k,l}$$a_{{k,l}}$, удовлетворяющий условиям $a_{k,l}=\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->m}{max}{a}_{i,l}=\underset{1\le <!--\; \le \; -->j\le <!--\; \le \; -->n}{min}{a}_{k,j}$$a_{k,l}=\max _{1\leq i\leq m}a_{i,l}=\min _{1\leq j\leq n}a_{k,j}$, то есть элемент матрицы, который одновременно является минимальным элементом в соответствующей строке матрицы и максимальным элементом в соответствующем столбце матрицы. Из определения следует, что $a_{k,l}=\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->m}{max}\underset{1\le <!--\; \le \; -->j\le <!--\; \le \; -->n}{min}{a}_{i,j}=\underset{1\le <!--\; \le \; -->j\le <!--\; \le \; -->n}{min}\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->m}{max}{a}_{i,j}$$a_{{k,l}}=\max _{{1\leq i\leq m}}\ \min _{{1\leq j\leq n}}a_{{i,j}}=\min _{{1\leq j\leq n}}\ \max _{{1\leq i\leq m}}a_{{i,j}}$. Более того, для матрицы существует седловой элемент тогда и только тогда, когда $\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->m}{max}\underset{1\le <!--\; \le \; -->j\le <!--\; \le \; -->n}{min}{a}_{i,j}=\underset{1\le <!--\; \le \; -->j\le <!--\; \le \; -->n}{min}\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->m}{max}{a}_{i,j}$$\max _{1\leq i\leq m}\ \min _{1\leq j\leq n}a_{i,j}=\min _{1\leq j\leq n}\ \max _{1\leq i\leq m}a_{i,j}$.

Аналогичным образом можно определить понятие седловая точка для любой функции от двух переменных: точка $(x^{\ast <!--\; \ast \; -->},y^{\ast <!--\; \ast \; -->})$$(x^{*},y^{*})$ является седловой точкой функции $f$$f$, определённой на декартовом произведении $X\times <!--\; \times \; -->Y$$X\times Y$, если

$f(x^{\ast <!--\; \ast \; -->},y^{\ast <!--\; \ast \; -->})=\underset{x\in <!--\; \in \; -->X}{max}f(x,y^{\ast <!--\; \ast \; -->})=\underset{y\in <!--\; \in \; -->Y}{min}f(x^{\ast <!--\; \ast \; -->},y)$$f(x^{*},y^{*})=\max _{x\in X}f(x,y^{*})=\min _{y\in Y}f(x^{*},y)$

ПримерыПравить

Матрица

${\begin{bmatrix}5&6&4&5\\-2&5&3&7\\8&7&-2&6\\\end{bmatrix}}$ 

имеет 1 седловой элемент, равный 4, который расположен в первой строке в третьем столбце матрицы, так как он одновременно является минимальным элементом в соответствующей строке матрицы (в данном случае в первой строке матрицы) и максимальным элементом в соответствующем столбце матрицы (в данном случае в третьем столбце матрицы).

Матрица

${\begin{bmatrix}2&3&5&2\\2&4&6&2\\-2&7&2&0\\\end{bmatrix}}$ 

имеет 4 седловых элемента, равных 2, которые расположены в первой строке в первом столбце, в первой строке в четвёртом столбце, во второй строке в первом столбце, во второй строке в четвёртом столбце матрицы, соответственно.

Данный пример показывает, что матрица может иметь несколько (более одной) седловых точек.

Тем не менее, если матрица имеет несколько седловых точек, то все их значения равны.

Так, в матрице, все элементы которой равны друг другу, все элементы являются седловыми точками.

Матрица

${\begin{bmatrix}3&2&1\\1&3&4\\\end{bmatrix}}$ 

не имеет седловой точки.

ПрименениеПравить

Вышеприведенное использование термина «седловая точка» имеет особое значение в теории игр. Так, например, в играх с нулевой суммой седловая точка платёжной матрицы является равновесием Нэша.