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.

I will explore more properties of the triangle product in a future post.