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

Question

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?

Answer 1

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