Construct Matrix with given Permanent

[Albert Chan]

Thread Happy New Year 2024 ... and 2023's last teaser !

(01-01-2024 08:29 PM)Maximilian Hohmann Wrote:  Hello!

For me, the complexity of the task to construct a matrix whose permanent has a given value by far exceeds the task of computing this permanent. As I have no idea at all about how to do it - and have never heard about "permanent" with respect to matrices before either - I asked my friend ChatGPT for help:

You: "Can you please compute a 12x12 matrix whose permanent is xxxx using only 0 and 1 as values"

ChatGTP: "Generating a specific 12x12 matrix with a permanent of xxxx using only 0 and 1 values involves finding an arrangement of elements such that their product sums up to xxxx when considering all possible permutations. The direct calculation of such a matrix might require a lot of computational effort due to the factorial complexity involved ...

Except for first row, we start with this:

[
            first row,
[0,0,0,0,0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0,1,1,1],
[0,0,0,0,0,0,0,0,1,1,1,1],
[0,0,0,0,0,0,0,1,1,1,1,1],
[0,0,0,0,0,0,1,1,1,1,1,1],
[0,0,0,0,0,1,1,1,1,1,1,1],
[0,0,0,0,1,1,1,1,1,1,1,1],
[0,0,0,1,1,1,1,1,1,1,1,1],
[0,0,1,1,1,1,1,1,1,1,1,1],
[0,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1]]

Permanent = total paths of 1's from top to bottom (different columns)

Permanent = 2^0 = 1 if first row is
[0,0,0,0,0,0,0,0,0,0,0,1]
[0,0,0,0,0,0,0,0,0,0,1,0]

Permanent = 2^1 = 2 if first row is
[0,0,0,0,0,0,0,0,0,1,0,0]

Permanent = 2^2 = 4 if first row is
[0,0,0,0,0,0,0,0,1,0,0,0]

Permanent = 2^3 = 8 if first row is
[0,0,0,0,0,0,0,1,0,0,0,0]

...

x = first row bits      → Permanent = (x//2) + (x%2)

Either of these as first row will produce Permanent = 2023 = 0b11111100111

[1,1,1,1,1,1,0,0,1,1,0,1]
[1,1,1,1,1,1,0,0,1,1,1,0]

To make puzzle challenging, we randomly swap rows and cols,
which does not change value of Permanent.

To solve puzzle, we undo randomization, to make above "standard form".
Then, we just read off first row pattern for Permanent.