Source: http://tamivox.org/redbear/gen_matrix_mult/index.html
Timestamp: 2019-04-23 07:54:23+00:00

Document:
A generalized multidimensional matrix multiplication.
Version of Tuesday 14 June 2016.
§ 1. Widely studied, and extensively used, is the matrix multiplication of elementary linear algebra. This operation takes two inputs that are two-dimensional (hereafter "2-D") matrices; the output is also a 2-D matrix.
a scalar can (but need not) be deemed 2-D with 1 row and 1 column.
Because matrices often contain many components, they are frequently manipulated by computer programs, often of a numerical nature. A programmer would use some sort of data structure, probably an array, to store the component information.
Can matrix multiplication be extended to matrices of three or more dimensions? Of course it can be, and it certainly has been. However, such operations are, relative to the 2-D version, infrequently seen. Moreover, there are various ways that multiplication for n-D matrices might be defined, and no one of them has risen to prominence. In this report, we offer a very general approach subsuming some of the definitions that already exist.
This report is an outgrowth of another project, the present author's mat_gen_dim, which developed an n-D array storage method for the C++ programming language. The manner of implementating therein the outer product, and of implementing n-D generalizations of contraction and the inner product, led to a broad definition of n-D matrix multiplication which deserved a separate mathematically-oriented description. The mat_gen_dim pages discuss the operations in a computer programming parlace, which reads altogether differently from this report.
As "generalized multidimensional matrix multiplication" is an unwieldy phrase, we will often use the symbol ⊕⊗ for the operation being defined. The rationale for this notation will become clear later.
Sections 2 through 5 of this report deal with preliminaries; ⊕⊗ itself is covered beginning in section 6. Note that we never denote any kind of multiplication by typographical juxtaposition, always preferring to use an explicit symbol of some sort.
§ 2. What is a matrix? A collection of components, typically numbers, which can be individually accessed by use of an index. "Individually accessed" means that reading or changing one component does not affect the others. Also, the value of one component does not constrain the set of possible values for other components.
An index is an ordered n-tuple of integers; without loss of generality we choose in this report to limit them to positive values. Every matrix has a fixed dimensionality, which is a nonnegative integer. If a matrix is n-dimensional, any index to be used with it must have exactly n elements. Note our terminology: matrices have components while indices have elements.
Many writers use the word subscript where we are using index, from the typographical custom of using subscripts for indices. We avoid that here because subscripts become difficult to read when indices are complicated, especially when subscripts themselves have subscripts. Another reason is that tensor algebra partitions an index's elements into opposing categories denoted by superscripts or subscripts, and we do not want to be appearing to suggest any tensorial interpretation. However, our approach to matrices can be used to carry out many operations of tensor algebra.
describes a 3-D matrix the index for any component of which must have three elements. The first element can be 1, 2, or 3; the second 1, 2, 3, 4, or 5; and the third 1, 2, 3, or 4. There are 60 = 3 × 5 × 4 possible combinations, all of which are valid, and each of which designates a different component of the matrix. Hence the matrix has 60 components, and this number will not change. We follow the popular mathematical convention that the minimum value of any index element can be 1; on the other hand are systems that always start with 0. Further, environments such as the Ada programming language and mat_gen_dim employ no universal base.
If matrix A has the index ranges above, a notation for a particular component is A[2, 1, 4], and for a general component is A[i1, i2, i3]. Note the square brackets for component selection. Meanwhile, A[2, 1, 4, 7] is wrong for having too many components, and A[2, 9, 4] is wrong for being out of range in the middle element. If the dimensionality of matrix B is denoted as b, an index for B can be written as B[i1, i2 … ib].
If matrix C has zero dimensions, its sole component is written C[ ]. Why one component and not zero? Because the number of components in a matrix is determined by multiplying the number of indices in each dimension, and the multiplicative identity for integers is one, not zero.
When all of a matrix's index ranges are equal, for instance (1 .. 7, 1 .. 7, 1 .. 7, 1 .. 7), we say that the matrix is equilateral. Any matrix of 0 or 1 dimensions is equilateral by convention. Although equilateral matrices are favored in tensor algebra, the matrix multiplication to be defined in this report has little need for for that characteristic. To emphasize that point, example matrices will be equilateral as little as possible.
§ 3. Two matrices are comorphic if they have the same dimensionality and the same ranges for respective index elements. Between two comorphic matrices, a component of the first corresponds to a component of the second if the two components have the same index.
Two comorphic matrices are equal if every component of the first equals the corresponding component of the second. Symbolically, A = B means that A[i1, i2 … id] = B[i1, i2 … id]. The mutual dimensionality of A and B is represented by d, and all in must (of course) be within their respective index ranges.
Symbolically, A + B = C means that A[i1, i2 … id] + B[i1, i2 … id] = C[i1, i2 … id].
For many operations, the notion of conformability can be defined. Broadly, it means that input matrices (and other items) have compatible dimensionalities, index ranges, et cetera. (Operations differ in their requirements, so "compatible" might not mean "equal".) In the case of addition, conformability is the same as comorphism.
If y is a scalar, A × y = B has the component-by-component meaning A[i1, i2 … id] × y = B[i1, i2 … id]. Meanwhile, division of a matrix by a scalar amounts to multiplying the matrix by the scalar's reciprocal. Any attempt to define the opposite operation, dividing a scalar by a matrix, poses many questions not easily answered.
Negation is no problem: −A = A × −1.
§ 4. The outer product takes two matrices as input and delivers one as output. The input matrices need not be of the same dimensionality, nor need their index ranges match in any way. Indeed, the outer product exists for any two matrices; and by induction, for countably many matrices. Hence comformability is assured. We use the circle-times symbol as a prefix notation for this operation; thus the outer product of A and B is written ⊗(A, B).
A[i1, i2 … ia] × B[j1, j2 … jb] = C[i1, i2 … ia, j1, j2 … jb].
Similarly, the index ranges of C are catenative of the index ranges of A and B. A lengthy example of the outer product is on a separate page.
The outer product has never gained much currency in the field of linear algebra. A likely reason is that although the outer product is often huge, it contains no more information than the factors that comprise it. Yet for us, it is a valuable steppingstone toward defining ⊕⊗.
§ 5. Besides the outer product, we need a contraction operation in order to establish ⊕⊗. As a preliminary we define the bunting, which is an ordered n-tuple of boolean values; we use Greek uppercase letters to represent buntings. Each boolean within the bunting is called a flag.
output: a matrix, called Y.
Of the two criteria to make contraction conformable, the first is that the number of flags in Φ must equal the dimensionality of X.
Individual flags can be addressed with square brackets: Φ, Φ, et cetera. The number of true flags is termed the dimensionality of the contraction. Our notation for contraction uses the circle-plus character in prefix position: ⊕(X, Φ) = Y.
The second of the two criteria for conformability is that all the index ranges corresponding to true flags must be equal. By contrast, the index ranges corresponding to the false flags need not equal anything in particular.
the dimensionality of the output matrix.
the X component's indices in the true positions all equal one another.
The no-true contraction is always legal, in other words, conformable. The one-true contraction is legal if X has at least one dimension. With more trues, index ranges must match.
If there are no trues, then Y will have the same dimensionality and index ranges as X, and will be filled with the additive identity, namely zero.
If the number of trues is more than 1, then some components of X will not be used.
No component of X will be an addend for more than one component of Y.
If there are no falses, then the sole component of Y will be the sum of the components of X's principal diagonal; this is a generalized trace.
Unless X is filled with zeroes, no combination of flags can cause Y to equal X.
Two 1-D contractions in succession generally give a result different from one 2-D contraction, and similarly for higher dimensionalities of contraction.
Contraction is distributive over addition: ⊕(A + B, Φ) = ⊕(A, Φ) + ⊕(B, Φ).
Let matrix A have the index ranges (1 .. 2, 1 .. 3, 1 .. 4, 1 .. 3, 1 .. 2).
Form matrix B1 by contracting A in the two dimensions that have subscript range 1 .. 3 (the second and fourth indices).
Form matrix B2 by contracting B1 in the one dimension that has subscript range 1 .. 4 (now the second index, but originally the third).
Form matrix C1 by contracting A in the one dimension that has subscript range 1 .. 4 (the third index).
Form matrix C2 by contracting C1 in the two dimensions that have subscript range 1 .. 3 (now the second and third indices, but originally the second and fourth).
Then B2 = C2. When a matrix is equilateral, or more nearly so, this principle still applies; but care is required to keep track of which indices are involved in which contractions, because indices are shifting to the left.
Calculate the outer product of any two or more matrices.
Perform any conformable contraction on that product.
Note that the ⊗ symbol was chosen for the outer product because its internal operation is multiplication; and ⊕ was chosen for contraction because its internal operation is addition. We suggest retaining the ⊕⊗ symbol sequence for this generalization of the multidimensional matrix product, because the characters are distinctive and they emphasize the bipartite nature of the operation; and because many kinds of matrix multiplication have been defined elsewhere, with notations of all sort.
§ 7. Any two or more n-D matrices have an outer product, and for any matrix there exists a bunting enabling a contraction. Therefore ⊕⊗ exists for any two or more matrices; depending on how many of their index ranges match, there may be several (but finitely many) valid ⊕⊗s, each with a different bunting. The choice of buntings is governed by the rules for conformability.
Let Φ = (false, true, true, false).
Elements of C that are completely ignored in the contraction are shaded in red in the table above; those used are shaded in green. This highlights the fact that, although the most convenient way to define ⊕⊗ is by way of an outer product followed by a contraction, such is far from the most efficient way to implement ⊕⊗. In matrices of practical size, the proportion of wasted calculation can easily exceed 99 percent. The mat_gen_dim software uses a direct approach to figure ⊕⊗ for two matrix inputs, the key function there being called inner_product. There, unused products are not calculated.
Each component of D is the dot product of one row of A and one column of B. Nomenclature varies, but the dot product is often termed "the" inner product or the "standard" inner product. Thus ordinary matrix multiplication, which yields a matrix full of dot products, might be regarded as a multidimensional generalization of the inner product. That explains why the mat_gen_dim software refers to ⊕⊗ by the name inner_product, although another reason is that the C++ language in which the software is written does not allow characters such as ⊕ and ⊗ in the names of functions. Our avenue of generalizing the inner product, by increasing the dimensionality, is separate from, but not in conflict with, the approach employed in the study of inner product spaces.
which is one contraction of the outer product of three matrices, as opposed to two contractions each being of an outer product of two matrices.
sin (A, Φ) = ⊕⊗(A1, Φ) ÷ 1!
− ⊕⊗(A3, Φ) ÷ 3!
+ ⊕⊗(A5, Φ) ÷ 5!
− ⊕⊗(A7, Φ) ÷ 7!
If we regard the components of A as a collection of variables, then ⊕⊗(An, Φ) becomes an nth-degree polynomial in those variables. Within the terms of the series, the dividends thus grow exponentially, but the divisors grow factorially, so all the respective matrix components will ultimately converge.
L is a left identity for a particular Φ when ⊕⊗(L, A, Φ) for all A.
R is a right identity for a particular Φ when ⊕⊗(A, R, Φ) for all A.
Some functions have more than one right identity, or more than one left identity. If a function has both a left identity and a right identity, they are equal, and there are no other identities.
For ⊕⊗, M is a right identity when Φ = (false, false, true, true, true, false), and is a left identity when Φ = (false, true, true, true, false, false), but neither case has a two-sided identity.
M is a right identity for ⊕⊗ when Φ = (falsed−1, trued, false1).
M is a left identity for ⊕⊗ when Φ = (false1, trued, falsed−1).
In two dimensions, the left and right identities merge, and the cosine becomes possible.
Beyond these, it is difficult to find any useful or interesting identity values in the equilateral associative environment.
In the left and middle members ⊗ is performed before ⊕, but in the right member ⊕ occurs before ⊗. Also, in the right member B no longer contributes to the contraction.
In these briefer notations, care must be exercised if A, B, or C is a 1-D matrix whose components happen to be booleans instead of numbers; then the matrix could be mistaken for a bunting.

References: § 1

§ 2

§ 3

§ 4

§ 5

§ 7