0

I'm trying to understand the following things.

Let $\{1, \dots , n\}:=[n]$ and consider multi-indices $\textbf{a,b} \in [n]^l$ for some integer $l$.

Let's define an equivalence relation $\textbf{a}\sim \textbf{b} \Leftrightarrow \textbf{a}_i = \textbf{a}_j \Leftrightarrow \textbf{b}_i = \textbf{b}_j \, \, \forall i,j \in [l].$ (equality patterns)

Which are the equivalence classes of a such relation? Can you provide me some simple examples even with $l=2$?

Let's say that $n=2, l=2$.

so if $\textbf{a} = (1,1) \Rightarrow \textbf{b} = (1,1)$ or $\textbf{b} = (2,2)$

if $\textbf{a} = (2,2) \Rightarrow \textbf{b} = (1,1)$ or $\textbf{b} = (2,2)$

if $\textbf{a} = (1,2) \Rightarrow \textbf{b} = (1,2)$ or $\textbf{b} = (2,1)$

if $\textbf{a} = (2,1) \Rightarrow \textbf{b} = (1,2)$ or $\textbf{b} = (2,1)$

This is what I manage to get but I still have several perplexities about which the equivalence classes are in this case.

James Arten
  • 1,953
  • 1
  • 8
  • 20
  • Please edit to include your efforts. If, say, $n$ is small then you should be able to list all the tuples by hand and simply check. – lulu Oct 11 '21 at 15:19
  • Ok I've just expanded out a simple case but I still have some perplexities :( – James Arten Oct 11 '21 at 15:32
  • So for $l=2$, you should be able to see all the cases. In general, you'll need to look at partitions of $l$, one block (of restricted size) in which no terms match, and then constant blocks. I'm not sure the characterization will be pleasant for large $n$. – lulu Oct 11 '21 at 15:34
  • but which are the equivalence classes? Why are they the partitions of $l$ in this case? – James Arten Oct 11 '21 at 15:37
  • Maybe since I only have two possible cases $(1,1) \sim (2,2)$ and the other where they are different then ok I have two different eqivalence classes. But is there a way to write them explicitly? – James Arten Oct 11 '21 at 15:52
  • On the paper I'm reading they write them to be $\gamma_1 ={{1}, {2}}$ and $\gamma_2 = {{1,2}}$ to refer when $i \neq j$ and $i =j$ respectively but I don't understand why. – James Arten Oct 11 '21 at 15:54
  • 1
    With $l=2$ the equivalence classes are just $(a,b)$ with $a\neq b$ and $(a,a)$. For higher $l$ I think it gets messy. – lulu Oct 11 '21 at 18:21
  • 1
    I take it back, it is not hard. For each $l-$tuple, partition it according to the digits (so all the $1's$ are in one block, and so on). The equivalence classes are just determined by these partitions (that is, two $l-$tuples are equivalent iff the partitions they give rise to are equivalent.). – lulu Oct 11 '21 at 18:29

1 Answers1

1

To summarize the discussion in the comments:

Given an $l-$tuple, $(a_1, \cdots, a_l)$ we define a partition of $\{1, \cdots l\}$ according to the digits in the tuple.

Thus, with $l=7, n=5$, the $6-$tuple $(3,3,5,1,3,5,3)$ we would get the partition $\{(1,2,5,7),\,(3,6), (4)\}$.

Then: two $l-$tuples are equivalent iff they define the same partition.

Indeed, the partition tells you precisely which "blocks" of indices must have a common digit.

Note: as an example, take $l=2$. There are only two partitions of $\{1,2\}$, namely $\{(1,2)\}$ and $\{(1),(2)\}$. The first gives you the pairs of the form $(a,a)$ and the second gives you the pairs of the form $(a,b)$ with $a\neq b$.

lulu
  • 70,402