How many different configurations can I achieve by rolling the colomns of a 3×4 matrix of integers

integersmatricespermutations

I have a 3×4 matrix of different integers (3 column, 4 rows), the integers are 0..11
Only rolling of the columns are allowed. How many possible, and different configurations exists?

What is the result if we take the rows into account as sets instead of arrays?

Example
Original matrix:

[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
[9, 10, 11]

Rolling the last column downward by 1:

[0, 1, 11]
[3, 4, 2]
[6, 7, 5]
[9, 10, 8]

Rolling the middle column downward by 2:

[0, 7, 2]
[3, 10, 5]
[6, 1, 8]
[9, 4, 11]

Best Answer

You can have four positions (configurations) for each column, and hence $4^3$.

Related Solutions

[Math] How do the rows of a change of basis matrix form a basis for expressing columns

This part is awfully explained in this article, but after some confusion eventually I came to following conclusions:

1) In the case of PCA we assume that our initial basis in which our data $X$ is expressed is identity matrix $I$ (which is orthonormal)

2) Then we apply following change of basis theorem( I am not going to prove this):

If P is a transition matrix from an orthonormal basis to another orthonormal basis,then P is orthogonal

3) In PCA data we assume that our new basis in which we will express our data is also orthonormal

4) Next theorem(easy to prove):

If A is an identity basis and B is our new basis, then change of basis matrix $P$ (from A to B): $P=B$

5)As a result of above theorems we can conclude that if we want to change orthonormal identity basis $A$ to some other orthonormal basis $B$, we have following properties: $$P=B$$ $$P^{-1}=P^{T}$$ $$B^{T}=P^{T}$$

6) So rows of our transformation matrix $P^{-1}=B^{T}$ from $A$ to $B$ are the columns(basis vectors) of our new orthonormal basis $B$. And this is fully consistent with PCA tutorial article.

Combinatorics – Number of Equivalence Classes of $w \times h$ Matrices Under Switching Rows and Columns

This has a very straightforward answer using the Burnside lemma. With $n$ rows, $m$ columns and $q$ possible values we simply compute the cycle index of the cartesian product group ($S_n \times S_m$, consult Harary and Palmer, Graphical Enumeration, section 4.3) and evaluate it at $a[p]=q$ as we have $q$ possibilities for an assignment that is constant on the cycle. The cycle index is easy too -- for two cycles of length $p_1$ and $p_2$ that originate in a permutation $\alpha$ from $S_n$ and $\beta$ from $S_2$ the contribution is $a[\mathrm{lcm}(p_1, p_2)]^{\gcd(p_1, p_2)}.$

We get for a $3\times3$ the following colorings of at most $q$ colors:

$$1, 36, 738, 8240, 57675, 289716, 1144836, 3780288,\ldots$$

which points us to OEIS A058001 where these values are confirmed.

We get for a $4\times 4$ the following colorings of at most $q$ colors:

$$1, 317, 90492, 7880456, 270656150, 4947097821, \\ 58002778967, 490172624992,\ldots$$

which points us to OEIS A058002 where again these values are confirmed.

We get for a $5\times 5$ the following colorings of at most $q$ colors:

$$1, 5624, 64796982, 79846389608, 20834113243925, 1979525296377132, \\ 93242242505023122, 2625154125717590496,\ldots$$

which points us to OEIS A058003 where here too these values are confirmed.

This was the Maple code.

with(combinat);

pet_cycleind_symm :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_cycleind_symmNM :=
proc(n, m)
local indA, indB, res, termA, termB, varA, varB,
    lenA, lenB, instA, instB, p, lcmv;
option remember;

    if n=1 then
        return pet_cycleind_symm(m);
    else
        indA := pet_cycleind_symm(n);
    fi;

    if m=1 then
        return pet_cycleind_symm(n);
    else
        indB := pet_cycleind_symm(m);
    fi;

    res := 0;

    for termA in indA do
        for termB in indB do
            p := 1;

            for varA in indets(termA) do
                lenA := op(1, varA);
                instA := degree(termA, varA);

                for varB in indets(termB) do
                    lenB := op(1, varB);
                    instB := degree(termB, varB);

                    lcmv := lcm(lenA, lenB);
                    p :=
                    p*a[lcmv]^(instA*instB*lenA*lenB/lcmv);
                od;
            od;

            res := res + lcoeff(termA)*lcoeff(termB)*p;
        od;
    od;

    res;
end;



mat_count :=
proc(n, m, q)

    subs([seq(a[p]=q, p=1..n*m)],
         pet_cycleind_symmNM(n, m));
end;

Addendum Nov 17 2018. Note that a product of powers of variables implements the multiset of cycles concept through indets (distinct elements) and degree (number of occurrences). Here we iterate over pairs of monomials representing a conjugacy class from $Z(S_n)$ and $Z(S_m)$ and compute $a[\mathrm{lcm}(p_1, p_2)]^{\gcd(p_1, p_2)}$ for pairs of cycles $a_{p_1}$ and $a_{p_2}.$ This makes for the highly compact algorithm shown above, which will produce e.g. for a three by four,

$${\frac {{a_{{1}}}^{12}}{144}}+1/24\,{a_{{1}}}^{6}{a_{{2}}}^{3} +1/18\,{a_{{1}}}^{3}{a_{{3}}}^{3}+1/12\,{a_{{2}}}^{6} \\+1/6\,{a_{{4}}}^{3}+1/48\,{a_{{1}}}^{4}{a_{{2}}}^{4} +1/8\,{a_{{2}}}^{5}{a_{{1}}}^{2}+1/6\,a_{{1}}a_{{2}}a_{{3}}a_{{6}} \\+1/8\,{a_{{3}}}^{4}+1/12\,{a_{{3}}}^{2}a_{{6}} +1/24\,{a_{{6}}}^{2}+1/12\,a_{{12}}.$$

Best Answer

Related Solutions

[Math] How do the rows of a change of basis matrix form a basis for expressing columns

Combinatorics – Number of Equivalence Classes of $w \times h$ Matrices Under Switching Rows and Columns

Related Question