# An optimization problem involving the calculation of MatrixRank as a constraint

I am dealing with an optimization problem that involves the rank of a matrix as a hard constraint. I am starting with this simple example

NMinimize[{a12, MatrixRank[{{a11, a12}, {2, 4}}] == 1 && a11 >= 1}, {a11, a12}]


That is a 2x2 matrix {{a11, a12}, {2, 4}} of which the first row is undetermined and I want to put a rank of 1 as a hard constraint. With another constraint, a11>=1, the answer would be  a12=2. However, it gives the following information

NMinimize::nsol: There are no points that satisfy the constraints {False}.


But the thing is, it seems that whenever evaluated in Mathematica with symbols, the command MatrixRank[{{a11, a12}, {2, 4}}] always gives 2 as an answer. Is there a way that can evaluate MatrixRank[{{a11, a12}, {2, 4}}] numerically inside the NMinimize function and solve the problem above?

As some people may point out, calculating the determinant can be an alternative. The reason that I prefer to use MatrixRank is that actually, the matrices I am dealing with can be rectangular as well. Even if it is nxn square, I may require its rank to be n-2.

A matrix loses rank whenever one of the singular values is zero. So you can solve:

Solve[SingularValueList[{{a11, a12}, {2, 4}}][[1]] == 0, {a11, a12}, Reals]

{{a12 -> 2 a11}}


which shows the relationship that must hold between a11 and a12 for the singular value (and hence the rank) to vanish.

• What if it is a matrix of a larger dimension, say 4x4 and I need the rank to be 2 or 4x5 and I need the rank of to be 2? Is there a way to generalize your idea of letting singular values to be zero consecutively? – nanjun Nov 17 '16 at 15:50
• If you want a 4D matrix to have rank two, then you could try solving for conditions when two of the singular values equal zero.Of course, at some point, this will stop working due to the complexity of the singular value computation. – bill s Nov 17 '16 at 16:21

That rank is already computed and it is not 1 (it is 2), hence the False issue. To get around that, delay the rank computation until numeric values are in place.

mrank[a1_?NumberQ, a2_?NumberQ] :=
MatrixRank[{{a1, a2}, {2, 4}}]
NMinimize[{a12, {mrank[a11, a12] == 1, a11 >= 1}}, {a11, a12}]

During evaluation of In[26]:= NMinimize::cvdiv: Failed to converge to a solution. The function may be unbounded.

(* Out[27]= {-3.3552524496*10^104, {a11 -> 1.08581705166,
a12 -> -3.3552524496*10^104}} *)


As can be seen that does not work out well either, because it is requiring a measure 0 condition. Better instead to keep smallest eigenvalue or singular value under some threshold. Could be done as below.

NMinimize[{a12, {Min[
Abs[Eigenvalues[{{a11, a12}, {2, 4}}]]] <= .0001,
a11 >= 1}}, {a11, a12}]

During evaluation of In[25]:= NMinimize::incst: NMinimize was unable to generate any initial points satisfying the inequality constraints {-0.0001+Min[1/2 Abs[4+a11-Power[<<2>>]],1/2 Abs[4+a11+Sqrt[Plus[<<4>>]]]]<=0}. The initial region specified may not contain any feasible points. Changing the initial region or specifying explicit initial points may provide a better solution.

(* Out[25]= {1.99974964841, {a11 -> 1.00000010102, a12 -> 1.99974964841}} *)

• I prefer your first idea of "delaying the rank computation until numeric values are in place". Can you explain about what is a "measure 0 condition" and why in this case it is not satisfied? One possible issue with your second idea may be if I am dealing with a matrix of larger dimension (square or rectangular), requiring the smallest singular value to be effectively 0 does not indicate anything about the second, the third... smallest one. Thus a nxn matrix may have rank n-1, n-2, ... which we do not know exactly I guess. – nanjun Nov 17 '16 at 16:34
• The parameters need to satisfy an algebraic relation in order for the rank not to be 2, and with MatrixRank it is an all-or-nothing situation. As for different ranks, can work with the nth sing value. – Daniel Lichtblau Nov 17 '16 at 17:13