# Decomposing a matrix into a sum of permutations

I have the following table where each row and column add to 100:

Position | A  | B  | C  |
---------+----+----+----+
1        | 20 | 50 | 30 |
2        | 30 | 20 | 50 |
3        | 50 | 30 | 20 |
---------+----+----+----+


I then need to create a value for each possible ordered combination of A,B,C (i.e. ABC, ACB, BAC, BCA, CAB, CBA) such that the above constraints are still met.

For example:

ABC relates to A in position 1, B in position 2 and C in position 3

and

ACB relates to A in position 1, C in position 2 and B in position 3

As these are the only two combinations that contain A in position 1 then the values for these two combinations should total 20 (position A1 in the table above).

But then ACB and BCA should total 50 as these are the only 2 combinations that contain C at position 2.

I'm not even sure if this is possible? I've tried simultaneous equations and think i'm finding more unknowns than equations which then means no solution right?

Anybody willing to take a stab at it and find a solution if ones exists?

• Open problems are problems that haven't been solved by anyone, not problems that just haven't been solved by you. That tag is inappropriate.
– Jam
Feb 4, 2020 at 11:39
• Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here. Feb 4, 2020 at 11:40
• More unknowns than equations just means that there is no unique solution. For example $x+y=10$ is one equation with two unknowns. There are an infinite number of possible solutions.
– tomi
Feb 4, 2020 at 11:49
• Do you have the further constraint that values must be integers only?
– tomi
Feb 4, 2020 at 11:50
• @tomi - No, the values don't have to be integers. They just have to be non-negative Feb 4, 2020 at 12:03

Suppose $$ABC = x$$. Then we have:

$$ABC + ACB = 20 \Rightarrow ACB = 20-x \\ ABC + CBA = 20 \Rightarrow CBA = 20-x \\ ABC + BAC = 20 \Rightarrow BAC = 20-x \\ BAC + BCA = 50 \Rightarrow BCA = 50-(20-x)=30+x \\ CBA + CAB = 30 \Rightarrow CAB = 30-(20-x)=10+x$$

Pick any value you like for $$x$$ and you have a solution. If you want all values to be strictly positive then $$0 < x < 20$$.

• Thank you, much simpler than i originally thought! Feb 4, 2020 at 13:43
a: ABC
b: ACB
c: BAC
d: BCA
e: CAB
f: CBA

import sympy as sy
a ,b, c, d, e, f, x, y, z = sy.symbols("a b c d e f x y z")

a = sy.solve(
[
(a+b)/(c+d) - 0.4,
(e+f)/(c+d) - 0.6,
(c+e)/(a+f) - 1.5,
(b+d)/(a+f) - 2.5,
(d+f)/(a+c) - 2.5,
(b+e)/(a+c) - 1.5
],
[a ,b, c, d, e, f])
print(a)


There is certainly more than one solution.

You can find one quite directly by considering the symmetries in the matrix. For instance, you need $$20$$ permutations where A is the first letter, $$20$$ where B is the second letter, and $$20$$ where C is the third letter, so $$20$$ ABC would cover that. In a similar fashion, $$30$$ CAB and $$50$$ BCA completely cover all $$100$$ words with no instances of the other three words.