Proof. The answer is 190017.
First, construct the following doubly stochastic matrix M: Divide M into four submatrices, where the first 75 rows and the first 24 columns form submatrix A, the last 25 rows and the first 24 columns form submatrix B, the first 75 rows and the last 76 columns form submatrix C, and the last 25 rows and the last 76 columns form submatrix D. The elements in A are all 751, the elements in B are all 0, the elements in C are all 190017, and the elements in D are all 761. It can be easily verified that M is a doubly stochastic matrix.
Assume that we can select 150 elements from
M such that the sum of the selected elements in each row and each column is greater than
190017. Let
a be the number of elements selected from
A and
d be the number of elements selected from
D. In the first 75 rows and the last 76 columns, there are at least
151−a−d rows and columns that do not contain selected elements from
A or
D. Among these rows and columns, there must be at least 2 selected elements from
C, as each selected element from
C contributes to exactly one row and one column. Therefore, the number of selected elements from
C is at least
2⋅(151−a−d)⋅21=151−a−d. Thus, the total number of selected elements from
A,C,D is at least
a+d+(151−a−d)=151, which is a contradiction. Hence,
λ≤190017.
To complete the proof, we need to show that λ=190017 satisfies the given conditions. Let M be any doubly stochastic matrix, and we call the elements of M not less than 190017 "large numbers".
If there exist 50 distinct large numbers that are not in the same row or column, we can assume that these 50 large numbers are in the first 50 rows and the first 50 columns by exchanging rows and columns if necessary. Then, we select the largest element from each of the last 50 rows (which is not less than 1001) and the largest element from each of the last 50 columns. In this way, we have selected at most 150 numbers, and the sum of the selected numbers in each row and each column is not less than 190017.
We now show that the above scenario always occurs. By contradiction, assume that there are no 50 distinct large numbers that are not in the same row or column. Then, by Hall's theorem in the deficiency form, we have:
(*) There exist k rows, 51≤k≤100, such that the large numbers in these k rows are distributed among at most k−51 columns.
Without loss of generality, assume that the large numbers in the first k rows are distributed among the first k−51 columns. Divide M into four submatrices using the first k rows and the first k−51 columns, similar to the construction in the previous proof, and denote them as A,B,C,D. Let S(A),S(B),S(C),S(D) be the sums of the elements
in these submatrices, respectively. The sum of the numbers in the first
k−51 columns is
k−51, i.e.,
S(A)+S(B)=k−51. Since the elements in
C are not large numbers, we have
S(C)<190017k(151−k). Moreover,
S(D)≤S(B)+S(D)=100−k. Therefore, we have:
100=S(A)+S(B)+S(C)+S(D)<(k−51)+190017k(151−k)+(100−k)≤49+190017⋅75⋅76=100,which is a contradiction.
Thus, we have shown that λmax=190017 satisfies the given conditions. □