# Matricization of a vector

Definitions

Define a vector Tuples[a[0, 1], n] of elements $$a[i_1,...,i_n], i_j \in \{0,1\} ~\forall j$$, that is for instance

{a[0, 0, 0, 0], a[0, 0, 0, 1], a[0, 0, 1, 0], a[0, 0, 1, 1], a[0, 1, 0, 0], a[0, 1, 0, 1], a[0, 1, 1, 0], a[0, 1, 1, 1], a[1, 0, 0, 0], a[1, 0, 0, 1], a[1, 0, 1, 0], a[1, 0, 1, 1], a[1, 1, 0, 0], a[1, 1, 0, 1], a[1, 1, 1, 0], a[1, 1, 1, 1]}

with n=4,

Define a set of tuples $$I_{l_k}\in \mathbb{R}^l$$ with $$l\in \{1,...,n-1\}$$ and $$k\in \{1,...,\binom{l}{n}\}$$. For instance with n=2, there is one possible value for $$l$$, that is $$l=1$$. Therefore, there exist 2 different tuple $$I_{1_1}=\{1\}$$ and $$I_{1_2}=\{2\}$$. For n=3, there is two possible value for $$l$$, that is $$l=1$$ and $$l=2$$. Therefore, for $$l=1$$ there exists 3 different tuple $$I_{1_1}=\{1\}$$, $$I_{1_2}=\{2\}$$ and $$I_{1_3}=\{3\}$$. For $$l=2$$, there exists 3 different tuple $$I_{2_1}=\{1,2\}$$, $$I_{2_2}=\{1,3\}$$ and $$I_{3_3}=\{2,3\}$$.

Goal

I would like to generate a matrix $$M_{I_{l_k}}$$ whose elements are the elements of the vector Tuples[a[0, 1], n], with respect to a given tuple $$I_{l_k}$$ in the following way : The rows are the elements of Tuples[a[0, 1], n] whose indices $$i_j$$ whose location $$j$$ is specified by the elements of the tuple $$I_{l_k}$$ are constant while the other indices vary from 0 to 1 in a binary order. The column are the elements of Tuples[a[0, 1], n] whose indices $$i_j$$ whose location $$j$$ is not specified by the elements of the tuple $$I_{l_k}$$ are constant while the other indices vary from 0 to 1 in a binary order.

Example

Here is the example for n=3. Since I can't write it in LaTeX here for some unknown reasons, this is a printscreen from a document. • I don't follow the generation of I, and I think it's because I don't understand k. Is k a member of the set Range[Binominal[n-1,n]]? Nov 14, 2022 at 14:21
• @IntroductionToProbability $k$ simply refer to the number of distinct ways one can choose $l$ elements of {1,...,n}. For a given $l$, there exist Binominal[n,l] possible ways to make this choice. Each one of this choice is represented by a tuple $I_{l_k}$ whose elements are the natural numbers chosen in {1,...,n}. Is it clearer ? If it suits you better, consider that k is an index that labels the different ways $I_l$ of choosing $l$ elements of {1,...,n}. Nov 14, 2022 at 14:52

I believe that this works:

mats[lLen_, nMax_] /; lLen < nMax := Module[
{
indices = Subsets[Range[1, nMax], {lLen}],
as = Nest[Partition[#, 2] &, Tuples[a[0, 1], nMax], nMax - 1]
},
Table[
Flatten[as, {ind, Complement[Range[1, nMax], ind]}],
{ind, indices}
]
]


Here is an explanation of the code.

1. The code snippet indices = Subsets[Range[1, nMax], {lLen}] generates the list of $$I_{l_k}$$'s, since $$I_l$$ really is just the list of subsets of $$\{1,\dots,n\}$$ that have size $$l$$.

2. The code snippet as = Nest[Partition[#, 2] &, Tuples[a[0, 1], nMax], nMax - 1] is the fastest (and just about most succinct) way I could come up with of generating the collection of a[ ... ]'s but nested in a way that would allow me to use an element of indices, i.e., one of the $$I_{l_k}$$'s, to automatically Flatten as in the correct way. Alternatively, as = ArrayReshape[Tuples[a[0, 1], nMax], ConstantArray[2, nMax]] works as well, and is perhaps easier to parse, but they seems equivalent in terms of speed. This basically forms an $$n$$-component tensor $$a_{i_1,i_2,\dots,i_n}$$ with $$i_j=0$$ or 1 and $$a_{i_1,i_2,\dots, i_n}=$$a[i_1,i_2,...,i_n]. In other words,

as[[i_1+1, i_2+1, ..., i_n+1]] = a[i_1,i_2,...,i_n]


so that the $$j$$'th index $$i_n$$ correspond to the jth level in the list as.

3. Finally, the heart of the code, which is Flatten[as, {ind, Complement[Range[1, nMax], ind]}]. I knew that Flatten should work, because it allows us to combine particular levels of a nested list in a controlled way. In addition, I knew that Tuples would generate the indices of a in the correct binary order, and that Partitioning the set should respect that order. After that, it was simply a matter of experimenting/guessing to see what works.

Here is how it works: From the documentation,

Flatten[list,{{s11,s12,...},{s21,s22,...},...}] flattens list by combining all levels sij to make each level i in the result.

Since the ith index of a is at the ith level of as, we just need to Flatten those levels that appear in I_{l_k} together (because the order of 0's and 1's will automatically be respected) and then Flatten the rest of the levels together (because again the order of 0's and 1's will automatically be respected).

So, ind in the Table is an iterator that picks out one element of indices, which is one of the $$I_{l_k}$$'s, and Complement[Range[1, nMax], ind]}] collects the rest of the indices. One way to think about the third argument of Flatten is that it chooses an order for the iterators first, and then chooses which levels to Flatten together. The order of the iterators is given by Join[ind, Complement[Range[1, nMax], ind]], which for $$I_{2_2}$$ for $$n=3$$ would be Join[{1, 3}, {2}] == {1, 3, 2}. After it's chosen this iteration order, it will then Flatten levels 1 and 3 to be level 1 in the list.

It's best to see an example. For $$n=3$$, as is

Nest[Partition[#, 2] &, Tuples[a[0, 1], 3], 3 - 1] The rows are the first level/index, and we can see that in each row, the values of $$i_1$$ in a[i_1,...] are all the same in each row. The columns are the second level/index, and we can see that in each column, all the $$i_2$$'s in a[i_1,i_2,i_3] are the same. Finally, the two-element lists in each matrix entry compose the third level/index, and we can see that the first element of each of these lists is a[i_1,i_2,0], whereas the second element of each list is a[i_1,i_2,1], indicating that the $$i_3$$'s are the same at the same spots in level 3.

Let's consider $$I_{2_2}=\{1,3\}$$. Then, taking ind to be {1, 3} and Complement[Range[1, 3], ind]}] to be {2}, we can see that Flatten iterates over indices 1 and 3 first, then over 2. That is to say, it chooses values of 1 and 3 first, then iterates over 2 to make the first row. For the first row, then, we fix the values of $$i_1$$ and $$i_3$$ to be 0, and iterate over $$i_2$$, leaving a[0, 0, 0] and a[0, 1, 0]. Thus, we see that the first and third indices of a are fixed in this row, with the second index iterated over in binary order (because binary order was automatically respected by Tuples and Partitioning), leaving the first row of $$M_{I_{2_2}}$$, which is • @Baloo This works on your test cases, and the you can test to see if it works more generally. If so, I can try to find the time to explain what's going on. The trick is that Flatten does amazing things. Nov 14, 2022 at 23:17
• Well, I don't know if you get those notifications, but I wrote 2 comments and deleted them because at first glance I didn't see how perfectly it fulfilled my expectations. Thanks a lot for your time, this is exactly what I looked for ! I would indeed be very interested to understand the tools and logic you used to write this :) Thanks again ! Nov 15, 2022 at 9:32
• @Baloo I've added an explanation. It might or might not make sense, but I've added what I think is the necessary explanation of what Flatten is doing, because that's the heart of the thing, combined with the proper partitioning of the original vector a. Nov 15, 2022 at 17:31
• Your explanation is really good, I learned a lot just by reading it. Thanks a lot for your time, you're awesome ! Nov 16, 2022 at 13:38