# Constrained total of rowwise maxima of a matrix

Suppose we have a matrix defined as follows: $$x=\begin{bmatrix} 9 & 8 & 1\\ 8 & 5 & 1\\ 1 & 1 & 8\\ \end{bmatrix}$$

x={{9,8,2},{8,5,9},{1,1,8}}


now, I am trying to implement a Mixed integer optimization program that returns the arguments (i.e., matrix indexes in the form of {{row-index,column-index},{row-index,column-index},...}, ordered by row-indexes) of the sum of the row-wise-maxima under the constraint that we can only take 1 element of each matrix row.

The solution is straightforward, taking

8+8+8=24


So the output should be

{{1,2},{2,1},{3,3}}


Note that the constraint bites here since an unconstrained problem just taking maximums of each row would yield

9+8+9=26


Also, note that my ideal program should also be enough flexible to maximize also non-symmetric matrices up to the trivial cases of vectors. For instance if

$$x=\begin{bmatrix} 9 & 8 \\ 8 & 5 \\ 1 & 1 \\ \end{bmatrix},$$ the program should report

{{1,2},{2,1}}}


And finally for $$x=\begin{bmatrix} 1 \\ 1 \\ 8 \\ \end{bmatrix},$$ the program should report

{{3,1}}


@rhermans already provided very useful work for row indexes. Unfortunately, my question was mis-specified in the beginning.

• Can you please clarify your example? Shouldn't unconstrained be Total[Max/@ x] giving $26$? Is the constraint that it can be only one of each different column? (instead you wrote "can only take 1 element of each matrix row." which is fulfilled by the unconstrained example.) Commented Dec 15, 2022 at 14:21
• Sorry for that typo
– oyy
Commented Dec 15, 2022 at 14:37
• Can you clarify if it is by columns or rows, is my answer what you expect? {2,1,3} are the indexes that give you 8+8+8 Commented Dec 15, 2022 at 14:38
• Just have a short question left. Assuming a non-symmetric matrix of the form x={{4,2},{1,1},{0,0}}, which should give {1,2}, how would I implement that?
– oyy
Commented Dec 15, 2022 at 14:56
• Perfect thanks!
– oyy
Commented Dec 15, 2022 at 15:02

# Old question

It feels you have not explained your requirements in enough detail, so you leave me guessing. This may be what you want.

The following code works only for square matrix

First@MaximalBy[
Permutations[Range[Length[x]]]
, Total@*MapIndexed[x[[#1,#2]]&]
]
(* {2,1,3}  *)


This is more general

First@MaximalBy[
Permutations[Range[Last@Dimensions[x]]]
, Total@*MapIndexed[x[[#1,#2]]&]
]


# New specification

The solution

f[xx_]:=Block[
{
indxl=Range[Last@Dimensions[xx]]
},
Transpose@{
indxl,
First@MaximalBy[
Permutations[indxl]
, Tr[xx[[#]]]&
]
}
]


The test matices

test = {
{{9,8,2},{8,5,9},{1,1,8}},
{{9,8},{8,5},{1,1}},
{{9},{8},{1}}
};


Now we get

f /@ test