1
$\begingroup$

I am trying to find a nice and efficient way to approach the following problem: I need to solve (for example using Solve, Reduce, or NSolve) certain type of equations involving a set of unknown square matrices, which have at most one non-zero element in each row and the sum of the $j$-th row across all matrices is equal to one. In other words, the unknown matrices have at most one most non-zero element in each row and the sum of the matrices is a row-stochastic matrix. How can I tell Mathematica to look only for these type of solutions?

Any ideas on how to elegantly enforce such constraints? Can I tell Mathematica in advance that the unknown matrices can only have one non-zero element on each row?

$\endgroup$
2
  • 1
    $\begingroup$ Can you provide some code and the objective function you're trying to minimize / solve? What have you tried so far? $\endgroup$
    – flinty
    Aug 2, 2021 at 11:16
  • $\begingroup$ Consider the long matrix mat formed by concatenating these horizontally. Then for all {i,j} you want to constrain 0<=.mat[[i,j]]<=1 and also Total[mat[[i]]]==1. $\endgroup$ Aug 2, 2021 at 13:32

1 Answer 1

1
$\begingroup$
T = {{{1, 0}, {0, 0}}, {{0, 0}, {0, 1}}};

(* Takes a list of matrices,
   must be an equation with == sign and must return True/False *)
equation[matrices_] := KroneckerProduct[T[[1]], matrices[[1]]] == KroneckerProduct[T[[2]], matrices[[2]]]

(* ensures rows have at most one non-zero element *)
mostonehot[row_] := Max[row^2] == Total[row^2]

(* the one-hot constraint but for all rows of a single matrix *)
sparsecons[mtx_] := AllTrue[mtx, mostonehot]

(* row-stochastic matrix constraint, so all rows should add to 1 *)
stochasticcons[mtx_] := Total[Transpose@mtx] == ConstantArray[1, Length@mtx]


matrices = Array[a, {2, 3, 3}]; (* e.g a list of 2 3x3 matrices *)
sol = First[matrices /. FindInstance[
    (* our equation must hold *)
    equation[matrices] &&
     (* sum of matrices must be row-stochastic *)
     stochasticcons[Total[matrices]] &&
     (* all matrices must have one-hot rows *)
     AllTrue[matrices, sparsecons]
    , Variables[matrices], NonNegativeReals]]

(** RESULT (no solution)
{{a[1, 1, 1], a[1, 1, 2], a[1, 1, 3]}, {a[1, 2, 1], a[1, 2, 2], 
  a[1, 2, 3]}, {a[1, 3, 1], a[1, 3, 2], a[1, 3, 3]}} **)
$\endgroup$
5
  • $\begingroup$ Thank you for the answer. This is more or less what I was looking for. I will accept shortly. I have a question though. I tried to look for a solution to an equation that I suspect does not have one and instead of getting the empty set as a response, I get back the first row of each of the unknown matrices "matrices"(in your code) which I am not sure how to interpret. What does such a response mean? $\endgroup$
    – AG1123
    Aug 4, 2021 at 5:52
  • $\begingroup$ @AG1123 you may need to provide the equation in an edit to your question. equation[...] must return True or False. If it's returning anything else then something is broken. $\endgroup$
    – flinty
    Aug 4, 2021 at 11:47
  • $\begingroup$ Let T={{{1,0},{0,0}},{{0,0},{0,1}}} and equation[matrices_]:= KroneckerProduct[T[[1]], matrices[[1]]]==KroneckerProduct[T[[2]], matrices[[2]]] which when combined with the constraints clearly has no solution. However, when I run your code for two $2\times 2$ matrices I get back {{a[1, 1, 1], a[1, 1, 2]}, {a[1, 2, 1], a[1, 2, 2]}}. $\endgroup$
    – AG1123
    Aug 4, 2021 at 13:07
  • $\begingroup$ @AG1123 that means there's no solution - if you remove the bit with First[matrices /. and just look at the output for FindInstance it gives an empty list - it's the replacement I've done that puts those symbols appearing in the result. $\endgroup$
    – flinty
    Aug 4, 2021 at 13:46
  • $\begingroup$ Oh yes, that makes sense. Thanks! $\endgroup$
    – AG1123
    Aug 4, 2021 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.