The Triangle Product for 3-Arrays

Wed 06 May 2015
Maths
#three-array

Lately, I have been thinking about vectors, matrices and linear algebra. Indeed, I have been thinking about higher-dimensional generalizations of matrices, i.e. from two-dimensional arrays of numbers to three-dimensional arrays of numbers. This was triggered by reading this blog post on tensors. In this post I will propose some generalizations to many of the properties of 2-arrays to the case of 3-arrays.

Orthotopic $k$-Arrays

A matrix is a rectangular array of elements. The 3-dimensional analog of a rectangle is the cuboid (also known as a 3-orthotope). Arranging elements into a cuboidal array yields what I will call a cuboidal 3-array. A square matrix is a special case where the 2-array has a square shape. The 3-dimensional analog of a square is the cube. Arranging elements into a cubic array yields what I will call a cubic 3-array.

More generally, the $k$-dimensional analog of a rectangle is the $k$-orthotope, and the $k$-dimensional analog of a square is the $k$-cube. Arranging elements into a $k$-orthotopic array yields an orthotopic $k$-array. Similarly, arranging elements into a $k$-cubic array yields a cubic $k$-array.

The discussion below will have the following form: I will first introduce a property of a 2-array, then I will propose the analog of the property for 3-arrays, and finally I will comment on the general case for $k$-arrays.

Size

The size of a rectangular 2-array $\mathbf{A}$ is given by a 2-tuple of natural numbers:

$$\operatorname{size}{(\mathbf{A})} = (m, n) \in \mathbb{N}^{2}.$$

Here $m$ is the number of rows, and $n$ is the number of columns. I will refer to $m$ as the capacity of the row-axis, and $n$ as the capacity of the column-axis. The set of all possible 2-arrays with size $(m, n)$ is denoted by $\mathbb{A}_{m \times n}$. The set of all possible rectangular 2-arrays is denoted by $\mathbb{A}_{2}$. It is given by

$$\mathbb{A}_{2} = \bigcup_{(m, n) \in \mathbb{N}^{2}} \mathbb{A}_{m \times n}.$$

The set of square 2-arrays is a subset of this space. The 2-tuples of natural numbers can be arranged in a semi-infinite triangular array, similar to Pascal's triangle:

$$(1, 1)$$

$$(1, 2) \quad (2, 1)$$

$$(1, 3) \quad (2, 2) \quad (3, 1)$$

$$(1, 4) \quad (2, 3) \quad (3, 2) \quad (4, 1)$$

$$(1, 5) \quad (2, 4) \quad (3, 3) \quad (4, 2) \quad (5, 1)$$

The 2-tuple on top of the triangle describes the size of 2-arrays that correspond to scalars (plain numbers). The left outer edge of the triangle describes the size of 2-arrays that correspond to row vectors. Similarly, the right outer edge of the triangle describes the size of 2-arrays that correspond to column vectors. Finally, the internal triangle, with $(2, 2)$ being on top, describes the size of rectangular 2-arrays.

In a similar manner, the size of an orthotopic 3-array $\mathbf{A}$ is given by a 3-tuple of natural numbers:

$$\operatorname{size}{(\mathbf{A})} = (a, b, c) \in \mathbb{N}^{3}.$$

I will refer to $a$ as the capacity of the 1-axis, to $b$ as the capacity of the 2-axis, and $c$ as the capacity of the 3-axis. The set of all possible orthotopic 3-arrays with size $(a, b, c)$ is denoted by $\mathbb{A}_{a \times b \times c}$. The set of all possible orthotopic 3-arrays is denoted by $\mathbb{A}_{3}$. It is given by

$$\mathbb{A}_{3} = \bigcup_{(a, b, c) \in \mathbb{N}^{3}} \mathbb{A}_{a \times b \times c}.$$

The set of cubic 3-arrays is a subset of this space. The 3-tuples of natural numbers can be arranged in a semi-infinite tetrahedral array, similar to Pascal's tetrahedron. The top vertex of this tetrahedron describes the size of 3-arrays that correspond to scalars. Each of the three edges from the top vertex correspond to the size of 3-arrays that correspond to vectors (three kinds now). Each of the three faces correspond to the size of 3-arrays that correspond to 2-arrays. The internal tetrahedron, with the 3-tuple $(2, 2, 2)$ being on top, describes the size of orthotopic 3-arrays.

More generally, the size of an orthotopic $k$-array $\mathbf{A}$ is given by a $k$-tuple of natural numbers:

$$\operatorname{size}{(\mathbf{A})} = t = (n_{1}, n_{2}, \ldots, n_{k}) \in \mathbb{N}^{k}.$$

I will refer to $n_{j}$ as the capacity of the $j$-axis. The set of all possible orthotopic $k$-arrays with size $t$ is denoted by $\mathbb{A}_{t}$. The set of all possible orthotopic $k$-arrays is denoted by $\mathbb{A}_{k}$. It is given by

$$\mathbb{A}_{k} = \bigcup_{t \in \mathbb{N}^{k}} \mathbb{A}_{t}.$$

The set of cubic $k$-arrays is a subset of this space.

Addition

Given two rectangular 2-arrays $\mathbf{A}$ and $\mathbf{B}$, both with size $(m, n)$, the operation $\operatorname{add}_{2}(\mathbf{A}, \mathbf{B})$ returns a third 2-array with size $(m, n)$. Thus,

$$\operatorname{add}_{2} : \mathbb{A}_{m \times n} \times \mathbb{A}_{m \times n} \longrightarrow \mathbb{A}_{m \times n}.$$

The elements of the 2-array $\operatorname{add}_{2}(\mathbf{A}, \mathbf{B})$ are found by element-wise adding the elements of $\mathbf{A}$ with the elements of $\mathbf{B}$. The addition operation on 2-arrays is commutative:

$$\operatorname{add}_{2}(\mathbf{A}, \mathbf{B}) = \operatorname{add}_{2}(\mathbf{B}, \mathbf{A}).$$

It is also associative:

$$\operatorname{add}_{2}(\operatorname{add}_{2}(\mathbf{A}, \mathbf{B}), \mathbf{C}) = \operatorname{add}_{2}(\mathbf{A}, \operatorname{add}_{2}(\mathbf{B}, \mathbf{C})).$$

In a very similar manner, you can define the operation $\operatorname{add}_{3}$, and more generally $\operatorname{add}_{k}$ for adding two $k$-arrays of the same size. These operations are also associative and commutative.

Cayley Transposition

A rectangular 2-array $\mathbf{A}$ with size $(m, n)$ has a total of $mn$ elements. These can be rearranged into a rectangular 2-array $T(\mathbf{A})$ with size $(n, m)$ by swapping the row-axis with the column-axis. This operation is called the Cayley transposition:

$$T: \mathbb{A}_{m \times n} \longrightarrow \mathbb{A}_{n \times m}.$$

The Cayley transposition is an involution:

$$T \circ T = I,$$

where $I$ is the identity operation. The operations $I$ and $T$ form $S_{2}$, the symmetric group of degree 2.

Similarly, an orthotopic 3-array with size $(a, b, c)$ has a total of $abc$ elements. These can be rearranged into five other orthotopic 3-arrays, corresponding to the $3! - 1 = 5$ permutations of its three axes. Thus, there are five Cayley transpositions:

$$T_{1}: \mathbb{A}_{a \times b \times c} \longrightarrow \mathbb{A}_{b \times a \times c},$$

$$T_{2}: \mathbb{A}_{a \times b \times c} \longrightarrow \mathbb{A}_{a \times c \times b},$$

$$T_{3}: \mathbb{A}_{a \times b \times c} \longrightarrow \mathbb{A}_{c \times b \times a},$$

$$T_{4}: \mathbb{A}_{a \times b \times c} \longrightarrow \mathbb{A}_{c \times a \times b},$$

$$T_{5}: \mathbb{A}_{a \times b \times c} \longrightarrow \mathbb{A}_{b \times c \times a}.$$

Three of these are involutions:

$$T_{1} \circ T_{1} = I, \quad T_{2} \circ T_{2} = I, \quad T_{3} \circ T_{3} = I.$$

The other two are each other's inverses:

$$T_{4} \circ T_{5} = I, \quad T_{5} \circ T_{4} = I.$$

The five Cayley transpositions and the identity operation form $S_{3}$, the symmetric group of degree 3.

More generally, an orthotopic $k$-array can be rearranged into $k! - 1$ different orthotopic $k$-arrays. Thus, you will have $k! - 1$ Cayley transpositions $T_{j}$. Only $k$ of these are involutions. Together with the identity element, the $k! - 1$ Cayley transpositions form $S_{k}$, the symmetric group of degree $k$.

Complex Conjugation

If a rectangular 2-array $\mathbf{A}$ has complex elements, then the complex conjugation operation $C$ returns a 2-array $C(\mathbf{A})$ with the same size as $\mathbf{A}$, but with element-wise complex conjugation. This operation is an involution:

$$C \circ C = I$$

The operation $C$ together with the identity operation form $S_{2}$, the symmetric group of degree 2.

Complex conjugation can be defined in the same way for 3-arrays, and also for $k$-arrays.

Hermite Transposition

The Hermite transposition operation $H$ on a rectangular 2-array $\mathbf{A}$ is defined by composing complex conjugation with Cayley transposition:

$$H(\mathbf{A}) = C \circ T(\mathbf{A}) = T \circ C(\mathbf{A}).$$

Hermite transposition on a 2-array is an involution. The operations $C$, $T$, $H$, and the identity form the group $S_{2} \times S_{2}$, which is equivalent to the dihedral group of order 4.

There are five Cayley transpositions on a 3-array, so there are five Hermite transpositions:

$$H_{j} = C \circ T_{j} = T_{j} \circ C.$$

Only three of these are involutions. The composition of two distinct Hermite transpositions is a Cayley transposition. The five Hermite transpositions, together with the five Cayley transpositions, $C$ and the identity operation form the group $S_{3} \times S_{2}$, which is equivalent to the dihedral group of order 12.

A similar story holds for $k$-arrays: you have $k! - 1$ Hermite transpositions, some of them are involutions, and together with the $k! - 1$ Cayley transpositions, the complex conjugation operation, and the identity operation they form the group $S_{k} \times S_{2}$ with $2 (k !)$ elements.

Multiplication

The 2-array multiplication operation $\operatorname{mul}_{2}$ takes a 2-array $\mathbf{A}$ with size $(m, p)$, and a 2-array $\mathbf{B}$ with size $(p, n)$, and returns a 2-array $\operatorname{mul}_{2}{(\mathbf{A}, \mathbf{B})}$ with size $(m, n)$. That is,

$$\operatorname{mul}_{2}: \mathbb{A}_{m \times p} \times \mathbb{A}_{p \times n} \longrightarrow \mathbb{A}_{m \times n}.$$

If the elements of $\mathbf{A}$ are denoted by $A_{\alpha \mu}$, the elements of $\mathbf{B}$ are denoted by $B_{\mu \beta}$, and the elements of $\mathbf{C} = \operatorname{mul}_{2}{(\mathbf{A}, \mathbf{B})}$ are denoted by $C_{\alpha \beta}$, then

$$C_{\alpha \beta} = \sum_{\mu = 1}^{p} A_{\alpha \mu} B_{\mu \beta}.$$

That is, the elements of $\mathbf{C}$ are found by contracting the column-axis of $\mathbf{A}$ with the row-axis of $\mathbf{B}$. It is for this reason that the capacity of the column-axis of $\mathbf{A}$ must equal the capacity of the row-axis of $\mathbf{B}$.

The multiplication operation satisfies the property

$$T(\operatorname{mul}_{2}{(\mathbf{A}, \mathbf{B})}) = \operatorname{mul}_{2}{(T(\mathbf{B}), T(\mathbf{A}))}.$$

This is how you distribute the Cayley transposition operation on a product of 2-arrays.

One way to motivate the 2-array multiplication operation is by viewing each rectangular 2-array as a line with two endpoints (i.e. a 1-simplex): the row-axis and the column-axis. The operation $\operatorname{mul}_{2}$ takes two lines and concatenates them to return another line. The concatenation contracts the column-axis of the first 2-array with the row-axis of the second 2-array.

I want the 3-array multiplication operation $\operatorname{mul}_{3}$ to return a 3-array. A 3-array has three axes. Viewing each orthotopic 3-array as a triangle (i.e. a 2-simplex), it appears one needs to concatenate three triangles to return another triangle. This leads me to introduce the triangle product operation, which is a ternary operation:

$$\operatorname{mul}_{3}: \mathbb{A}_{a \times p \times q} \times \mathbb{A}_{p \times b \times r} \times \mathbb{A}_{q \times r \times c} \longrightarrow \mathbb{A}_{a \times b \times c}.$$

Let $\mathbf{A}$ be a 3-array with size $(a, p, q)$, $\mathbf{B}$ be a 3-array with size $(p, b, r)$, and $\mathbf{C}$ be a 3-array with size $(q, r, c)$. The triangle product $\mathbf{D} = \operatorname{mul}_{3}{(\mathbf{A}, \mathbf{B}, \mathbf{C})}$ is a 3-array with size $(a, b, c)$. The elements of $\mathbf{D}$ are given by

$$D_{\alpha \beta \gamma} = \sum_{\mu = 1}^{p} \sum_{\nu = 1}^{q} \sum_{\rho = 1}^{r} A_{\alpha \mu \nu} B_{\mu \beta \rho} C_{\nu \rho \gamma}.$$

Here are more details:

The 1-axis of $\mathbf{A}$ survives as the 1-axis of $\mathbf{D}$.
The 2-axis of $\mathbf{A}$ is contracted with the 1-axis of $\mathbf{B}$.
The 3-axis of $\mathbf{A}$ is contracted with the 1-axis of $\mathbf{C}$.
The 2-axis of $\mathbf{B}$ survives as the 2-axis of $\mathbf{D}$.
The 3-axis of $\mathbf{B}$ is contracted with the 2-axis of $\mathbf{C}$.
The 3-axis of $\mathbf{C}$ survives as the 3-axis of $\mathbf{D}$.

The triangle product satisfies these properties:

$$T_{1}(\operatorname{mul}_{3}{(\mathbf{A}, \mathbf{B}, \mathbf{C})}) = \operatorname{mul}_{3}{(T_{1}(\mathbf{B}), T_{1}(\mathbf{A}), T_{1}(\mathbf{C}))},$$

$$T_{2}(\operatorname{mul}_{3}{(\mathbf{A}, \mathbf{B}, \mathbf{C})}) = \operatorname{mul}_{3}{(T_{2}(\mathbf{A}), T_{2}(\mathbf{C}), T_{2}(\mathbf{B}))},$$

$$T_{3}(\operatorname{mul}_{3}{(\mathbf{A}, \mathbf{B}, \mathbf{C})}) = \operatorname{mul}_{3}{(T_{3}(\mathbf{C}), T_{3}(\mathbf{B}), T_{3}(\mathbf{A}))},$$

$$T_{4}(\operatorname{mul}_{3}{(\mathbf{A}, \mathbf{B}, \mathbf{C})}) = \operatorname{mul}_{3}{(T_{4}(\mathbf{C}), T_{4}(\mathbf{A}), T_{4}(\mathbf{B}))},$$

$$T_{5}(\operatorname{mul}_{3}{(\mathbf{A}, \mathbf{B}, \mathbf{C})}) = \operatorname{mul}_{3}{(T_{5}(\mathbf{B}), T_{5}(\mathbf{C}), T_{5}(\mathbf{A}))}.$$

This is how you distribute the Cayley transpositions on a triangle product of 3-arrays. These are natural generalizations of the property for 2-arrays.

Presumably, for the case of $k$-arrays, the multiplication operation $\operatorname{mul}_{k}$ takes $k$ orthotopic $k$-arrays and returns another orthotopic $k$-array. The contraction is done in such a way as to preserve the $k$-simplex structure.