# Why are matrices ubiquitous but hypermatrices rare?

I am puzzled by the amazing utility and therefore ubiquity of two-dimensional matrices in comparison to the relative paucity of multidimensional arrays of numbers, hypermatrices. Of course multidimensional arrays are useful: every programming language supports them, and I often employ them myself. But these uses treat the arrays primarily as convenient data structures rather than as mathematical objects. When I think of the generalization of polygon to $d$-dimensional polytope, or of two-dimensional surface to $n$-dimensional manifold, I see an increase in mathematical importance and utility; whereas with matrices, the opposite.

One answer to my question that I am prepared to acknowledge is that my perception is clouded by ignorance: hypermatrices are just as important, useful, and prevalent in mathematics as 2D matrices. Perhaps tensors, especially when viewed as multilinear maps, fulfill this role. Certainly they play a crucial role in physics, fluid mechanics, Riemannian geometry, and other areas. Perhaps there is a rich spectral theory of hypermatrices, a rich decomposition (LU, QR, Cholesky, etc.) theory of hypermatrices, a rich theory of random hypermatrices—all analogous to corresponding theories of 2D matrices, all of which I am unaware.

I do know that Cayley explored hyperdeterminants in the 19th century, and that Gelfand, Kapranov, and Zelevinsky wrote a book entitled Discriminants, Resultants and Multidimensional Determinants (Birkhäuser, Boston, 1994) about which I know little.

If, despite my ignorance, indeed hypermatrices have found only relatively rare utility in mathematics, I would be interested to know if there is some high-level reason for this, some reason that 2D matrices are inherently more useful than hypermatrices?

I am aware of how amorphous is this question, and apologize if it is considered inappropriate.

-
Just a guess, but it may have to do with the difficulty of defining a (canonical) product of hypermatrices; you can't view them naturally as linear maps between vector spaces, and define a product via composition. –  Gordon Craig Dec 2 '10 at 13:25
If tensors are ubiquitous, and tensors are hypermatrices, then aren't hypermatrices ubiquitous? (Not a rhetorical question. I can't tell which of these statements you believe less.) –  Qiaochu Yuan Dec 2 '10 at 14:20
Here is a related question (related at least in my mind). Why are groups, rings and fields far more ubiquitous than sets $S$ equipped with a function $f:S \times S \times S \to S$ having "nice" properties? –  Louigi Addario-Berry Dec 2 '10 at 15:01
Furthermore, $n$-tuples are immensely more common than matrices... –  Gerald Edgar Dec 2 '10 at 15:16
I think this is also linked with the fact that while in many contexts a matrix is just a special case of a hypermatrix (e.g., representation of tensors, as above observed) there are also many cases where a multi-analog is really of less interesting generality. For instance, ternary or n-ary relations are definitely less used than binary relations; hypergraphs are not so widely used as graphs; linear maps between direct sums of vector spaces are rather a particular case than a generalization of linear maps between vector spaces. –  Pietro Majer Dec 2 '10 at 18:28

Note that in linear algebra matrices describe at least two different things: linear maps between vector spaces (we consider only finite-dimensional vector spaces here) and bilinear forms. When thinking of matrices as tensors, linear maps between $V$ and $W$ are elements of the space $V^* \otimes W$, whereas bilinear forms between $V$ and $W$ are elements of $V^* \otimes W^*$. Now you can easily generalize the latter case to more than two spaces, but not the former. But it is the former case where several concepts like composition (matrix multiplication), determinants, eigenvalues etc. apply. (Note that eigenvalues and determinants can be defined for bilinear forms on a vector space equipped with an inner product, but not for bilinear forms on plain vector spaces). Of course you can consider spaces like $V^* \otimes W^* \otimes X$, but elements of this space are better thought as linear maps between $V\otimes W$ and $X$ than as three-dimensional hypermatrices. So what is special about the number 2 is that there is a notion of duality for vector spaces, but no "n-ality".

-
Related to this, there is a very fruitful interplay between graphs and matrices, particularly with the use of eigenvalues of adjacency matrices. One can say a few things along these lines about hypergraphs, but they are (to date) much less satisfactory. –  gowers Dec 2 '10 at 15:49
@Florian: Your point about duality is a great insight! –  Joseph O'Rourke Dec 2 '10 at 16:11
Recent paper on spectral hypergraph theory, for eigenvalues of adjacency hypermatrices: "Spectra of Hypergraphs", Joshua Cooper, Aaron Dutle, arxiv.org/abs/1106.4856 –  Roy Maclean Sep 2 '11 at 15:40

To such a complex problem, there cannot be unique answer. I see many, which all justify the tremendous interest that mathematicians have devoted so far to matrices, rather than to hypermatrices.

Ubiquity. Matrices are used by every species of mathematicians, and beyond, by a large fraction of scientists. This is perhaps the only mathematical area to enjoy this versatility. Let me provide a few examples. Matrix exponential is fundamental in differential equation (more generally in dynamical systems) and Lie theory of groups. Symmetric matrices are used in quantum mechanics, statistics, optimisation and numerical analysis; they have deep relations with representation theory and combinatorics (see the solution of Horn's conjecture by Tao \& Knutson). Positive matrices are encountered in probability and numerical analysis (discrete maximum principle). Matrix groups are used in representation theory, in number theory (including modular forms), in dynamical systems (because of symmetries). When depending on parameters, matrices enter in PDE theory as symbols.

Simplicity. The concept of matrix is by definition simpler than that of hypermatrices. It is natural that the study of matrices precedes that of HM. This argument will fade as time increases, of course.

Richness. What makes a field particularly attractive is that it involves several apparent unrelated concepts in order to produce unexpected results. This happens in matrix theory, because on the one hand, we may view them as linear maps (where conjugation is relevant) and on the other hand we may see them as bilinear or sesquilinear maps (where congruence is relevant). It becomes especially fruitful when we go back and forth between both points of view. This happens in the remarkable theorem that normal matrices are unitary diagonalizable, but also in the parametrization of a Lie group by its Lie algebra via the exponential and the Hermitian square root. I am not at all aware of the theory of HM, but if they do not form naturally an algebra, I doubt that their theory could be so rich, or if it is, it will be for completely different mathematical reasons.

To temperate this pledge, let me say that hypermatrices have been studied (although not so deeply) under the name tensors. They are of great importance in differential geometry (Ricci curvature tensor, with the many identities named after Christoffel, Gauss, Codazzi, ...) and in its applications: general relativity, elasticity. These are undoubtedly difficult topics, where even simple problems are not well understood. To mention one of them, there is still no satisfactory description of the twice-symmetric tensors of fourth order ($a_{ijkl}=a_{jikl}=a_{ijlk}$) that satisfy the Legendre-Hadamard condition $$\sum_{i,j,k,l}a_{ijkl}x_ix_j\xi_k\xi_l\ge0,\qquad\forall x\in\mathbb R^n,\xi\in\mathbb R^d.$$ It seems to me that the use of HM is too scattered, and therefore there is no research community specializing on all their aspects. Edit. Likewise, the notion of rank, although correctly defined in the case of tensors, is hard to manipulate and to compute explicitly. This is the reason why the exact algorithmic complexity of the multiplication of matrices is still not known (the operation $(A,B)\mapsto AB$ in $M_n(k)$ may be viewed as a $3$-tensor, and its tensorial rank governs the number of operations needed in an $n\times n$ mulitplication).

-
@Denis: I could not ask for a more knowledgeable and informative answer. Your points about richness are especially enlightening. I am grateful! –  Joseph O'Rourke Dec 2 '10 at 15:25
The Legendre-Hadamard condition is a great example of what Gjergji asked in the comments above, one where the multilinear setting is much less understood than the linear case. Whereas it is well known that the convex cone generated by $\xi\otimes\xi$ "squares of vectors" in the space of square matrices is equivalent to the cone of positive semi-definite matrices, and as such that PSD cone is self-dual, an analogous statement is known to be false for Legendre-Hadamard tensors. –  Willie Wong Dec 2 '10 at 15:33
In particular, it'd be great to find out what is the difference set between the Legendre-Hadamard tensors and the rank-one cone generated by elements of the form $x\otimes x\otimes\xi\otimes\xi$, or even find a self-dual cone sitting between the two convex cones. –  Willie Wong Dec 2 '10 at 15:35

An awfully simplistic answer: we work on two-dimensional paper, so two-dimensional matrices are very convenient to write down and compute with, while higher-dimensional hypermatrices are not.

So while we could represent multilinear forms, tensors, etc. as hypermatrices, we often don’t, because doing so is not nearly as fruitful as representing linear maps, bilinear forms etc. as matrices. Instead, we usually use other notations when working with higher tensors by hand.

In computer algebra, the dimension of the paper is not significant, while some kinds of abstraction are harder, so in this context, higher tensors are much more often represented as hypermatrices.

-
I really think this is the answer. –  Allen Knutson Dec 2 '10 at 18:22
And the fact that we are speaking of this now, when computers make it easier to treat hypermatrices, seems to me a sort of confirm of ypur thesis. –  Pietro Majer Dec 2 '10 at 19:34
I do not think this is the answer. –  Gil Kalai Dec 6 '12 at 20:07
I'm sure that the comparative awkwardness of notation for hypermatrices at least partly explains their lack of popularity amongst mathematicians, and lack of popularity leads to lack of theory. So I think this answer is partly correct, but it needs to be combined with answers like Florian's that expose genuine features that differ for $D=2$ and $D>2$. –  Brendan McKay Dec 6 '12 at 22:37

I think much of what I'm about to say has been said already, but I wanted to repeat it: I don't agree with the premise of the question at all. A "hypermatrix" is simply another name for a tensor. All aspects of matrix operations that I know (multiplication, determinant, etc.) have direct generalizations to tensors. All of this is best developed and understood in the abstract setting using tensor and exterior algebras over abstract vector spaces, as well as representation theory. Moreover, tensors along with these operations are used in many settings, including but not restricted to algebraic and differential geometry. What is true is that you don't necessarily have the depth of theorems that you have for matrices, but my view is that is because of two reasons: 1) Tensors are more general, so they don't satisfy all of the properties of matrices, and 2) Tensors are more complicated, so it is takes longer to develop them to the same depth.

-
This is pretty much exactly the answer I would have given. I'd add one more reason: 3) it's harder to write the data of a tensor on a chalkboard or piece of paper. –  Theo Johnson-Freyd Dec 2 '10 at 21:58
Theo, an excellent point! –  Deane Yang Dec 2 '10 at 22:29
Theo, I just said a week ago to colleagues of mine (partly joking, but not entirely) that I specialized on matrices because I can write them on the blackboard. –  Denis Serre Dec 3 '10 at 3:57
I entirely agree with you, and I think Theo makes a very good point. I don't think I've ever seen a concrete tensor... –  Mozibur Ullah Dec 6 '12 at 21:44

Bhargava explained Gauss composition of binary quadratic forms using 2x2x2-cubes, which can be identified with 2x2x2-hypermatrices on which $SL_2({\mathbb Z})^3$ acts naturally; the hyperdeterminant of this hypermatrix is the common discriminant of the three associated quadratic forms. Already Cayley realized the connection with composition of binary quadratic forms.

-

One reason linear algebra is so useful is that the basic notions, like rank, have so many equivalent definitions. Some are better for formulating problems, some for proving theorems, and some for doing computations. The ability to freely move between these is the key to solving many problems.

Some of these definitions of course won't make sense for hypermatrices, but many of them do. The problem is that they don't usually end up being equivalent.

For example: you can define rank one hypermatrices as outer products of vectors ("simple tensors") and define the minimum number of such terms which must be summed to yield a given hypermatrix to be the "hyperrank". But this does not properly classify all hypermatrices up to changes of basis along all the "axes" of the hypermatrix as it does for matrices (in fact the number of equivalence classes is no longer even finite). And except in very simple cases this does not agree with what you'd get by the vanishing of certain "hyperdeterminants" -- indeed, the set of hypermatrices with hyperrank at most $k$ isn't even closed.

So the things you can compute aren't the same as the things you'd like to compute, and everything ends up feeling much more ad hoc.

Of course this complexity makes for a lot of interesting things to study, but not a simple widely applicable tool every undergrad should learn. Though perhaps they should learn why they don't learn it!

-

It seems to me is that there are a lot of things in mathematics that one could call hypermatrices if one were so inclined, but which people generally don't (and if they call them anything, they call them tensors). For example, one use of matrices $M$ is that they represent bilinear forms $x^T M y$ and quadratic forms $x^T M x$. Three-dimensional hypermatrices then represent trilinear forms and cubic forms (and so forth for higher dimensions), and these do appear in various places in mathematics, for example in Lie theory. The norm map on a cubic number field is also an example of a cubic form. More generally, alternating multilinear forms appear as differential forms, and the same can be said about more general types of tensors. It could be said that studying a projective hypersurface defined by a homogeneous polynomial $f(x_1, ... x_n) = 0$ is the same as studying a certain $n$-dimensional hypermatrix associated to $f$. It could be said that studying a finite-dimensional algebra or Lie algebra $A$ is the same as studying the hypermatrix giving the structure constants of its multiplication or bracket $m : A \times A \to A$.

So, as I said in the comments, I'm not sure what you mean when you say that hypermatrices are rare. I suppose you are trying to draw a distinction between basis-dependent and basis-independent ideas?

-

Although the following paper: Most tensor problems are NP Hard by Hillar and Lim does not explain why tensors are not so ubiquitous, it suggests that they might continue remaining non-ubiquitous. There seem to be no easy generalizations of standard notions in the matrix case: eigenvalues, singular value, spectral norm, etc., are shown two be NP-Hard to compute, even for 3-D tensors.

-

Since a matrix is just how we write down a linear map $V\to W$ from one vector space to another, it seems to me that the prevalance of matrices over hypermatrices is just a reflection of the fact that we use categories so much more often than multicategories (where a morphism has a list of objects as its domain). And I feel that the large role categories play, with morphisms that just go from one object to another, is due to the way we look at the world in terms of states and processes, of where you are now and how to get where you're going, of being and becoming.

Of course, by using duals of vector spaces we can also use matrices to represent either functionals $V\otimes W\to k$ or elements $k\to V\otimes W$, but I feel that these uses are usually no more special than their generalizations for hypermatrices.

-

I think that the difference between matrices and hypermatrices is closely related to the difference between graphs and hypergraphs.

1) Many of the miracles for graphs/matrices (characterization, duality, efficient algorithms) do not extend to high dimensions. Gauss elimination and the efficincy of computing determinants is at the roots of some of these miracles.

2) For modeling, in many cases graphs /matrices suffices. You can model a hypergraph easily using a graphs.

-

Hi Joseph,

it seems that the basic difference between hypermatrices and matrices is the indexation.

Let me explain what I mean. Consider a finite graph $G=(V,E)$ (the graph structure is not important I mentioning this just to refer to some geometrical interpretation of the index) and a collection of numbers $$(A_{v,w})_{(v,w)\in V\times V}.$$

Despite this list have a "two dimensional" character (bi-indexed) it is in fact a hypermatrice.

The way to import to hypermatrices the results of standard theory of matrix is to define the operations as usual. The product, for instance, is $$(AB)_{(v,w)}=\sum_{z\in V}A_{v,z}B_{z,w}.$$

The determinant and other important objects can also be defined in this way by replacing the group $\mathbb{S}_n$ by automorphisms of $V$ and so on.

So I guess that do not pop up any interesting feature that justify to give a great attention to this object. Because one can see them just as a replacement of the indexation process.

For the other hand in fields like statistical mechanics and percolation they are much more natural in high dimensional problems than the usual matrices. When we define $p_{uv}$ the probability to see the edge $\{u,v\}$ open or when we are leading with the coupling constants $J_{i,j}$ in the Ising model, all of them are hypermatrices and its linear algebra structure are frequently arise in proofs of important results in correlations inequalities.

-