3
$\begingroup$

Here is a conundrum I am facing.

I have $2$ matrix building blocks.

In my problem, I associate integer $2$ with $3\times 3$ matrix $A$ with structure \begin{bmatrix} 0& a& 0\\ c& 0& b\\ 0& d& 0 \end{bmatrix} and I associate integer $3$ with $4\times 4$ matrix $B$ \begin{bmatrix} 0& a& d& 0\\ i& 0& e& f\\ i& b& 0& c\\ h& g& g& 0 \end{bmatrix} and since we know that every integer $n>3$ is sum of some number of $2$ and $3$, my goal is given $n\in\Bbb N_{>3}$ I want to build an $n\times n$ matrix of given decomposition by recursively using these matrices as building brick. For example, to integer $4=2+2$, I will associate $4$ different $A$ matrices $A1,A2,A3,A4$ (each with distinct set of variables - not just $a,b,c,d$) and build \begin{bmatrix} 0& A1& 0\\ A3& 0& A2\\ 0& A4& 0 \end{bmatrix} to integer $5=3+2$, I will associate nine different $A$ matrices $A1,A2,A3,A4,A5,A6,A7,A8,A9$ (each with distinct set of variables - not just $a,b,c,d$) and build \begin{bmatrix} 0& A1& A4& 0\\ A9& 0& A5& A6\\ A9& A2& 0& A3\\ A8& A7& A7& 0 \end{bmatrix}

The submatrix corresponding to $0$ are just appropriately sized all zero matrices.

However for $10\times 10$ we have seven different constructions corresponding to $10=2+2+2+2+2=3+3+2+2=3+2+3+2=3+2+2+3$$=2+3+3+2=2+3+2+3=2+2+3+3$. Program should build according to the specified decomposition.

Is there a nice way to get such building operations?

Say if I want to build for $n\leq100$, I will apriori know how many variables $a,b,\dots$ I would need.

$\endgroup$
  • $\begingroup$ This sounds interesting, but can you further explain how the matrices are constructed from smaller ones? What should be the dimensionality of the matrices? How do you decide what matrix elements are zero? Etc. $\endgroup$ – march Sep 20 '15 at 23:02
  • $\begingroup$ It is as I have explained. Nothing more to it. Given a decomposition of $n$, build a matrix. $0$s are accordingly filled. $\endgroup$ – user32682 Sep 20 '15 at 23:05
  • 2
    $\begingroup$ I think you should read your question carefully and try to imagine someone reading it who is completely unfamiliar with your work. I am sure there is a nice way to do what you want, and I think it can be interesting, and you have provided good detail (I have upvoted the question), but it is really not clear what the construction is exactly. $\endgroup$ – march Sep 20 '15 at 23:10
  • $\begingroup$ What is unclear? $\endgroup$ – user32682 Sep 20 '15 at 23:10
  • $\begingroup$ Let me put it like this: I couldn't even tell ordering was relevant, but now that you say that, I think I might begin to understand. The matrix always has the structure of A or B matrices, with A or B matrices as sub matrices. That said, the ordering is very important, and when you add more than two "integers", it's definitely not obvious how to define the resulting matrix. Can you include an example for adding three integers or at least say something about how they are recursively defined? $\endgroup$ – march Sep 20 '15 at 23:24
5
$\begingroup$

Edit: The matGen and matBuildAux codes are updated moving the null arrays into the module variable, offering slight readability improvements and even slighter performance improvement on very large submatrices.


This is more of an extended comment than an answer because, as @march has pointed out multiple times, there is more detail required to frame your question.

To get you started, here is a function to generate the two matrices you describe when the variables/submatrices are known

Clear[matGen]
matGen[inits_List] /; AllTrue[inits, AtomQ] && Length[inits] == 4 := 
 {{0, inits[[1]], 0}, {inits[[3]], 0, inits[[2]]}, {0, inits[[4]], 0}}
matGen[inits_List] /; Length[inits] == 4 := 
 Module[{null = ConstantArray[0, Dimensions[inits[[1]]]]}, 
  {{null, inits[[1]], null}, 
   {inits[[3]], null, inits[[2]]}, 
   {null, inits[[4]], null}} // ArrayFlatten]
matGen[inits_List] /; AllTrue[inits, AtomQ] && Length[inits] == 9 := 
 {{0, inits[[1]], inits[[4]], 0}, 
  {inits[[9]], 0, inits[[5]], inits[[6]]}, 
  {inits[[9]], inits[[2]], 0, inits[[3]]}, 
  {inits[[8]], inits[[7]], inits[[7]], 0}}
matGen[inits_List] /; Length[inits] == 9 := 
 Module[{null = ConstantArray[0, Dimensions[inits[[1]]]]}, 
  {{null, inits[[1]], inits[[4]], null}, 
   {inits[[9]], null, inits[[5]], inits[[6]]}, 
   {inits[[9]], inits[[2]], null, inits[[3]]}, 
   {inits[[8]], inits[[7]], inits[[7]], null}} //ArrayFlatten]

These are a lazy attempt at generating the matrices and contain very few guards on the input. They mostly assume they're being fed an appropriate list of initial values where:

  1. The List argument is a list containing all the initial values/matrices to build the matrix.
  2. An A matrix will come from a list of 4 elements, while a B matrix comes from a list of 9 elements.
  3. If the elements of List are not atomic(symbols or numbers usually), then they are equally-sized square matrices.

Examples:

arr = Array[(#1 - 1) 2 + #2 &, {2, 2}];
matGen[{arr, arr, arr, arr}]//MatrixForm
matGen[{a, b, c, d, e, f, g, h, i}]//MatrixForm

Examples output

How to proceed with the recursive generation then seems rather ambiguous, given the current information, since you have stated that variables/submatrices in the composition are not the same. This leads to the necessity of specifying the initial values for all the submatrices involved at the first level. Just looking at something like the $3+3+2+2$ example, that requires specifying up to $9\times 9\times 4\times 4=1296$ different values for the initial iteration. Further, if the intermediate matrices and all of these values are unique then there needs to be a means of specifying which sets of values are associated with the submatrices at each position, a constraint which needs clarification in your problem description.

If for any reason you were interested in identical submatrices, then this function could take the decomposition represented as an ordered List and the initial values as an appropriately-sized List.

Clear[matBuildAux]
matBuildAux[elem_, 2] := 
 Module[{null = ConstantArray[0, Dimensions[elem]]}, 
  {{null, elem, null},     
   {elem, null, elem}, 
   {null, elem, null}} //ArrayFlatten]
matBuildAux[elem_, 3] := 
 Module[{null = ConstantArray[0, Dimensions[elem]]}, 
  {{null, elem, elem, null}, 
   {elem, null, elem, elem}, 
   {elem, elem, null, elem}, 
   {elem, elem, elem, null}} // ArrayFlatten]

Clear[matBuild]
matBuild[decomp_List, inits_List] /; 
  Which[Last[decomp] == 3, Length[inits] == 9, Last[decomp] == 2, Length[inits] == 4] := 
   Fold[matBuildAux, matGen[inits], Reverse[Most[decomp]]]

Here's an example

matBuild[{2, 2, 3}, {a, b, c, d, e, f, g, h, i}] // MatrixForm

second example output

$\endgroup$
4
$\begingroup$

New version

I believe this is closer to the OP's intent, although I am still having trouble parsing it completely. Here is what I think the OP wants:

  • The recursive structure as defined in the old version of the code below.

  • If matrix 3 is the last matrix embedded, then each copy of matrix 3 that gets embedded each has its own set of variables, but within each copy of matrix 3, the variables that are repeated (i and g in the example) are truly repeated.

  • If matrix 3 is embedded above the last level, then each matrix that ends up being embedded in positions i and g must be exactly the same, including the names of the variables. This is the only thing that makes sense to me.

For the purposes of illustration, I have replaced matrix 3 with a smaller version,

mat[3] = {{a[1], a[2]}, {a[2], 0}};

Note that I am repeating a[2] in order to mimic the behavior of the original in terms of the repeated variables. You may recover the old version using

mat[3] = {{0, a[1], a[2], 0}, {a[3], 0, a[4], a[5]}, {a[3], a[6], 0, a[7]}, {a[8], a[9], a[9], 0}};

If these suppositions are correct, then the following code works:

Clear[f, twoOrThree, a]
twoOrThree[x_] := x == 2 || x == 3
f[pat : {__?twoOrThree}] := Module[{mat, mats}
  , mat[2] = {{0, a[1], 0}, {a[2], 0, a[3]}, {0, a[4], 0}}
  ; mat[3] = {{a[1], a[2]}, {a[2], 0}}
  ; mats = mat /@ pat
  ; Fold[
     ArrayFlatten[#1 /. a[x__] :> (#2 /. a[y_] :> a[x, y])] &
     , First@mats
     , Rest@mats
  ]
 ]

For instance, f[{2, 3}] yields

enter image description here

f[{3, 2}] yields

enter image description here

(Notice that the sub-matrices in the upper right and lower left are identical, including the names of the variables.) Evaluating f[{3}], f[{3, 2}], and [f{3, 2, 3}] yields

enter image description here

(Notice that the sub-matrices in the upper right and lower left are identical, even though there is multiple nesting going on below the top level which is where the first instance of matrix 3 occurs.)

Finally, if the variable names with nested indices is annoying, we can always replace the distinct variables using

replaceVariables = #2 /. Thread[#1 -> Array[a, Length@#1]] & @@ {Variables@#, #} &;

Then, for instance,

replaceVariables@f[{3, 2}] // Grid

yields

enter image description here

Old version: every matrix element is its own variable

I couldn't resist.

Clear[f, twoOrThree,a]
twoOrThree[x_] := x == 2 || x == 3
f[pat : {__?twoOrThree}] := Module[{mat, mats, i = 1}
  , mat[2] = {{0, a, 0}, {a, 0, a}, {0, a, 0}}
  ; mat[3] = {{0, a, a, 0}, {a, 0, a, a}, {a, a, 0, a}, {a, a, a, 0}}
  ; mats = mat /@ pat
  ; Fold[
    ArrayFlatten[#1 /. a -> #2] &
    , First@mats
    , Rest@mats
    ] /. {a :> a[i++]}
  ]

The input is the list of 2's and 3's, in order of outside-in. I leave it to you to generate those lists.

The input is protected in the sense that it requires a list of 2's and 3's. For example,

f[{1, 2, 3}]
(* f[{1, 2, 3}] *)

However, evaluating f[{2, 3}] yields

enter image description here

and evaluating f[{3, 2}] yields

enter image description here

Post-script

It is likely that you should be using SparseArray objects, because the matrices are sparse, and they will grow pretty fast with the number of integers in the partition. I will try to work on a version that uses them, but in the code above they cannot be directly implemented.

$\endgroup$
  • $\begingroup$ That increment on the delayed rule in the old code is a slick trick. I was struggling with a way to distinguish the initial values. +1 $\endgroup$ – IPoiler Sep 21 '15 at 14:56
  • $\begingroup$ @It'sPronouncedOiler. I've seen similar types of things here and there on this site (and perhaps even this exact construction), so I just adapted it to my needs, but yeah, it's slick. Still, I'm pretty sure that the OP is looking for more something along the lines of the newer solution, given those repeated variables in Matrix 3. We'll see what the OP has to say. $\endgroup$ – march Sep 21 '15 at 15:42
  • $\begingroup$ I think so too. I'm mainly impressed because as long as I've used MMA I consistently overlook how simple, unique quirks can make my code cleaner, like the fact that Set and Pre/PostIncrement actually return passable values in addition to manipulating memory. As for OP's needs, I think you have an excellent method for tracking value positions and depths, the next step I've been considering (that I assume OP wants) is to be able to specify the integer sum and index the decompositions (maybe something similar to factoradic indexing for permutations). $\endgroup$ – IPoiler Sep 21 '15 at 16:44
  • $\begingroup$ @It'sPronouncedOiler. OP is looking for specific types of integer partitions, so maybe there's a lazy (CS-style, not actually lazy) way of generating integer partitions only consisting of 2's/3's, then writing down all permutations of each partition. Brute force way is to generate all integer partitions using IntegerPartition, then Selecting those that contain 2's or 3's. However, to my mind, this post is about constructing the matrices, and I feel like the OP is just asking us to do their work, so I'm unwilling to put in more effort. $\endgroup$ – march Sep 21 '15 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy