# How to enforce constraints on matrix equations for unknowns to have only one non zero element per row?

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?

• Can you provide some code and the objective function you're trying to minimize / solve? What have you tried so far? Aug 2, 2021 at 11:16
• 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. Aug 2, 2021 at 13:32

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[], matrices[]] == KroneckerProduct[T[], matrices[]]

(* 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]}} **)

• 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? Aug 4, 2021 at 5:52
• @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. Aug 4, 2021 at 11:47
• Let T={{{1,0},{0,0}},{{0,0},{0,1}}} and equation[matrices_]:= KroneckerProduct[T[], matrices[]]==KroneckerProduct[T[], matrices[]] 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]}}. Aug 4, 2021 at 13:07
• @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. Aug 4, 2021 at 13:46
• Oh yes, that makes sense. Thanks! Aug 4, 2021 at 15:17