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?

Improve this question
$\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$ Commented 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$ Commented Aug 2, 2021 at 13:32

1 Answer 1

Reset to default
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]}} **)
Improve this answer
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented Aug 4, 2021 at 13:46
  • $\begingroup$ Oh yes, that makes sense. Thanks! $\endgroup$ Commented Aug 4, 2021 at 15:17

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.