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.

[Albert Chan]

(01-03-2024 05:53 PM)Albert Chan Wrote:  To solve puzzle, we undo randomization, to make above "standard form".
Then, we just read off first row pattern for Permanent.

VA Square Matrix Permanent Puzzle
VA Solution posted yesterday, so this is not a spoiler anymore.

> m := [
[1,0,1,1,1,0,1,1,1,1,1,1],
[0,0,1,1,0,0,0,0,0,1,0,1],
[1,0,1,1,0,0,0,1,0,1,1,1],
[0,0,1,0,0,0,0,0,0,1,0,0],
[1,0,1,1,1,1,1,1,1,1,1,1],
[0,0,1,1,0,0,0,0,0,1,1,1],
[1,0,1,1,1,0,0,1,0,1,1,1],
[0,1,0,1,1,1,1,1,1,1,0,1],
[1,0,1,1,0,0,0,0,0,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1],
[0,0,1,0,0,0,0,0,0,1,0,1],
[1,0,1,1,1,0,1,1,0,1,1,1]]

> s:=map(sum,m)      → [10,4,7,2,11,5,8,9,6,12,3,9]

If Permanent Puzzle setup as I predicted, "first row" has 9 1's
We make them slightly different for sorting purpose.

> s[0]:=9.5
> m:=map(sort(s), k->m[index(s,k)])

\(\left(\begin{array}{cccccccccccc}
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 & 0 & 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
\end{array}\right)\)

> SWAPCOL(m,10,12)
> SWAPCOL(m,3,11)
> SWAPCOL(m,4,9)
> SWAPCOL(m,3,8)
> SWAPCOL(m,1,7)
> SWAPCOL(m,3,6)
> SWAPCOL(m,1,4)
> SWAPCOL(m,1,3)
> SWAPCOL(m,1,2)

\(\left(\begin{array}{cccccccccccc}
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 \\
1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 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
\end{array}\right) \)

"First row" bits (if we move 8th row to top) for Permanent

> 0b11111100110 + 1

2023

[Maximilian Hohmann]

Hello Albert,

I was about to suggest that you make your method public but you beat me to it! Now it becomes a lot clearer.

Thank you!
Max

[Albert Chan]

We can use DSU (Decorate Sort Undecorate) to avoid manually swapping columns.

Starting from original puzzle m

> m:=concat(transpose(map(sum,m)), m)
> m:=sort(m)
> DELCOL(m,1)
> m:=transpose(m)

Do the same for its transpose

> m:=concat(transpose(map(sum,m)), m)
> m:=sort(m)
> DELCOL(m,1)
> m:=transpose(m)

\(\left(\begin{array}{cccccccccccc}
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 \\
1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 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
\end{array}\right) \)

> horner(m[8],2)      → 4045
> ceiling(Ans/2)        → 2023 // = permanent(m)

[Albert Chan]

(01-04-2024 01:01 PM)J-F Garnier Wrote:  If you look closely at my solution, you will see that I sorted the array rows by the number of 1 in each row, not by the value of the binary representation:

20 DATA 0,0,1,0,0,0,0,0,0,1,0,0
21 DATA 0,0,1,0,0,0,0,0,0,1,0,1
22 DATA 0,0,1,1,0,0,0,0,0,1,0,1
23 DATA 0,0,1,1,0,0,0,0,0,1,1,1
24 DATA 1,0,1,1,0,0,0,0,0,1,1,1
25 DATA 1,0,1,1,0,0,0,1,0,1,1,1
26 DATA 1,0,1,1,1,0,0,1,0,1,1,1
27 DATA 0,1,0,1,1,1,1,1,1,1,0,1
28 DATA 1,0,1,1,1,0,1,1,0,1,1,1
29 DATA 1,0,1,1,1,0,1,1,1,1,1,1
30 DATA 1,0,1,1,1,1,1,1,1,1,1,1
31 DATA 1,1,1,1,1,1,1,1,1,1,1,1

This was the most important part of my 'optimization'
...
I did notice the structure of the sorted array and the exception of row 8 (of the sorted array),
but without paying too much attention to it.

If we sort columns the same way, then move red row to top, we have "standard form"

But, we don't need actual sorting.
Columns zeros count can be used to locate where red cells are, if sorted.

> r := [0,1,0,1,1,1,1,1,1,1,0,1];   /* red row */
> z := [4,10,0,2,6,9,7,5,8,0,3,1]; /* column zeroes count, without red row */
> r * 2^z                                    /* permanent(m), note: * is dot product */

2023

[Albert Chan]

A follow up of previous post example, to produce recursive formula for permanent(m)

PM to JFG Wrote:Imagine row 8 is all 1's, and we move that to the end

20 DATA 0,0,1,0,0,0,0,0,0,1,0,0
21 DATA 0,0,1,0,0,0,0,0,0,1,0,1
22 DATA 0,0,1,1,0,0,0,0,0,1,0,1
23 DATA 0,0,1,1,0,0,0,0,0,1,1,1
24 DATA 1,0,1,1,0,0,0,0,0,1,1,1
25 DATA 1,0,1,1,0,0,0,1,0,1,1,1
26 DATA 1,0,1,1,1,0,0,1,0,1,1,1
27 DATA 1,0,1,1,1,0,1,1,0,1,1,1
28 DATA 1,0,1,1,1,0,1,1,1,1,1,1
29 DATA 1,0,1,1,1,1,1,1,1,1,1,1
30 DATA 1,1,1,1,1,1,1,1,1,1,1,1
31 DATA 1,1,1,1,1,1,1,1,1,1,1,1

1st row has 2 paths
After we pick a 1 from 1st row, 2nd row has 2 paths
After we pick a 1 from 2nd row, 3rd row has 2 paths
...
After we pick a 1 from 10th row, 11th row has 2 paths
After we pick a 1 from 11th row, 12th row has 1 paths

P of this matrix = 2^(12-1) = 2048

Back to original puzzle, if we flip row 8 bits (0↔1), code would calculate 2048-P
DATA required sorting bit population, we get this new setup:

20 DATA 0,0,1,0,0,0,0,0,0,1,0,0
21 DATA 0,0,1,0,0,0,0,0,0,1,0,1
22 DATA 1,0,1,0,0,0,0,0,0,0,1,0
23 DATA 0,0,1,1,0,0,0,0,0,1,0,1
24 DATA 0,0,1,1,0,0,0,0,0,1,1,1
25 DATA 1,0,1,1,0,0,0,0,0,1,1,1
26 DATA 1,0,1,1,0,0,0,1,0,1,1,1
27 DATA 1,0,1,1,1,0,0,1,0,1,1,1
28 DATA 1,0,1,1,1,0,1,1,0,1,1,1
29 DATA 1,0,1,1,1,0,1,1,1,1,1,1
30 DATA 1,0,1,1,1,1,1,1,1,1,1,1
31 DATA 1,1,1,1,1,1,1,1,1,1,1,1

Red Line goes from bit population of 9, down to 3.
Also, it get moved up the matrix, reduced search space.
With this setup, code run much faster (~ 5X)

We get 2048-P = 25      → P = 2023

Let f(x) = permanent of "standard form" matrix m, with first row bits = x
Let n = bit_length of x                // leading zeroes ignored

f(2^n-1) = 2^(n-1)                    // explained in quote      
f(x) = 2^(n-1) - f(2^n-1 - x)      // 2nd term argument = flip(x), smaller than x
f(x) = x, if x = 0 or 1                  // base case

(01-03-2024 06:06 PM)Albert Chan Wrote:  "First row" bits (if we move 8th row to top) for Permanent

> 0b11111100110 + 1

2023

f(0b111111001101)
= 2^11 - f(0b110010)
= 2^11 - 2^5 + f(1101)
= 2^11 - 2^5 + 2^3 - f(0b10)
= 2^11 - 2^5 + 2^3 - 2^1 + 1
= 2048 - 32 + 8 - 2 + 1
= 2023