Minimax Principle

Let's first of all formalize the procedure. We start with an array A_i,k of numbers. By convention, the first index designate a row, the second a column. For example, element A_3,5 is located in the row number 3 and the column # 5. Keep the first index fixed - this is to say, select a row (the row corresponding to the fixed first index.) Denote the minimum element in this row as B_i = Min(A_i,k). (The minimum is taken over all k for a fixed i.) The result generally depends on the selected row. Denote the maximum number among B_i's as MaxMin = Max(B_i). (The maximum is taken over all i's.)

In a similar manner, let C_k = Max(A_i,k), where, as before, maximum is taken over all i's (for a fixed k, i.e., for a fixed column.) Compute then MinMax = Min(C_k).

Statement

1. MinMax MaxMin
2. The equality is achieved iff there exists an element A_i0,k0 that is simultaneously maximal in its column and minimal in its row.

Proof

Writing subscripts in HTML (this is the language of the Web) is somewhat awkward. Let's just agree that Max is taken over index i, whereas Min is always taken over index k.

Assume MinMax = A_{i0 ,k0} for some indices i₀ and k₀. MinMax = Min(C_k) = C_k0. In other words, MinMax is the maximum element in column k₀. By definition, C_k0 = Max(A_{i, k0}). Every element A_i,k0 in column k₀ may or may not be the smallest number in its row. But, in any event, the smallest number in a row can't exceed any element in that row:

Ai,k0 Min(Ai, k) = Bi

Combining that with

Ai0, k0 = Max(Ai, k0) Ai, k0

(which is just a different way of describing our selection of indices) we get

Ai0,k0 Min(Ai,k) = Bi

The left hand side in the latter does not depend on the index i, and the inequality holds for any value of i (any row in the table.) Therefore, maximizing the right hand side will preserve the inequality:

(1)	MinMax = Ai0,k0 Max(Bi) = MaxMin

which proves the first part of the statement.

To prove the second part, first assume that MinMax = MaxMin. Then (1) becomes

which means that the element A_{i0, k0} (=MinMax) is also equal to MaxMin.

Conversely, assume there exists an element A_i0,k0 such that

Ck0 = Max(Ai, k0) = Ai0, k0 = Min(Ai0, k) = Bi0

Then, by definition,

MaxMin = Max(Bi) Bi0 = Ck0 Min(Ck) = MinMax

However, as we have shown in the first part of the proof, MinMax  MaxMin always, which gives MinMax = MaxMin.

The point (i₀, k₀) such that MinMax = A_i0,k0 = MaxMin is called a saddle point for a given table A. Saddle points may exist for functions of continuous arguments as well. Graphs of such functions in a vicinity of a saddle point in fact resemble the shape of a saddle.

The saddle points have interesting properties that you may observe with the applet and also try proving:

1. If there are more than one saddle point, then all corresponding matrix entries coincide.
2. If there are two saddle points at (i₁, j₁) and (i₂, j₂), such that i₁ differs from i₂ and j₁ differs from j₂, then (i₁, j₂) and (i₂, j₁) are also saddle points.