Quivers: a year of linear algebra by drawing arrows
Disclaimer: if your first instinct was to think about string diagrams, that's not was this post is about. Cool guess, though.
In algebra there's this idea of representations of some object, especially linear representations. It's so important that even chemists typically have the representation theory of finite groups in their curriculum, because those have a profound influence on the structure of atoms and molecules.
And it just so happens that studying representations of a particular kind of object (namely, quivers) can be seen as a generalization of a typical 1-year university linear algebra course :)
First, lets talk about representations a bit more.
The idea is that some objects are easier to study and understand than others. For example, permutations are easier to work with than elements of a general group, and there's a theorem that any group can be represented as a group of some permutations.
One of the things we understand the best in math are matrices — they seem to be in the perfect sweet spot between showing up everywhere and also having a deep, rich, and useful theory. It turns out that we can represent many objects as matrices, in which case we call them linear representations, though often the word representation means a linear representation by default.
As a simple example, consider complex numbers: how can we represent the number \(i\) as a real-valued matrix? Well, \(i\) is defined as being a root of the equation \(i^2=-1\), so we just need to find a matrix that satisfies this equation. Note that we'll need to replace the number \(-1\) with the scalar matrix having \(-1\) on the diagonal (because this matrix effectively acts as the number \(-1\) in the matrix algebra).
It's not hard to find a matrix which squares to \(-1\):
\[ \begin{pmatrix}0 & -1 \\ 1 & 0\end{pmatrix}^2 = \begin{pmatrix}-1 & 0 \\ 0 & -1\end{pmatrix} \]
You can notice that it's the matrix of rotation by \(90^\circ\), and that's not a coincidence!
If we also represent real numbers \(a\) as scalar matrices \(\begin{pmatrix}a & 0 \\ 0 & a\end{pmatrix}\), we can represent the complex number \(a+bi\) as a matrix
\[ a+bi \mapsto \begin{pmatrix}a & -b \\ b & a\end{pmatrix} \]
and matrices of this form act exacly like complex numbers — the addition and multiplication formulas are the same, as are all the other properties (the technical term is that the algebra of such matrices is isomorphic to the complex numbers).
In general, representations are easiest to define via category theory. For example, take a group, turn it into a one-object category with elements of this group as morphisms (i.e. categorify the group to obtain a groupoid), and then representations of this group are simply functors from this groupoid into some other category. Functors to \(\operatorname{Set}\) give permutation representations, while functors to \(\operatorname{Vect}_K\) give linear representations.
I want to stress one thing which might sound like obvious truth, a boring technicality, or useless garbage, depending on your background. We commonly represent vectors using coordinates, which is especially convenient for direct computations, but an abstract vector isn't the same as a list of coordinates. We can always choose a different basis, and the coordinates of a specific vector will change, but the vector itself won't change — it represents some specific (albeit abstract) geometric object which doesn't depend on a particular encoding scheme that we've arbitrarily chosen.
The same goes for matrices and operators. A matrix is just a table with numbers; it only means something geometric once we've selected the basis vectors — specifically, it means a linear operator acting on these vectors. If we change the basis, the vectors and operators don't change, but the vector coordinates and matrix entries can change.
How important this is depends entirely on your domain of work. I'm bringing this up because it does matter here: by choosing a basis in a clever way, we can see how some complicated object ends up looking very simple. In fact, keeping track of bases will be very important in what follows.
So, what exactly is a quiver? It's a directed graph. That's it, that's the definition.
OK, there are a dozen different things that people call a directed graph
. Does it allow for multiple edges? Does it allow loops? For a quiver, the answers are yes and yes. In other words, there are no restrictions on edges: there can be several edges between two vertices, and edges can start and end in the same vertex. This type of a directed graph is often called a multidigraph.
Here are a few examples of quivers:
These were made with an online tool called — you wouldn't believe it — q.uiver.app.
Ok, a quiver is a multidigraph, i.e. a directed graph with multi-edges and loops allowed. If we already have a name for it, why call them quivers?
It boils down to the perspective that we're interested in. If you want to find shortest paths, count connected components, check if it is planar, etc, you'd call it a multidigraph. But if you're interested in representations and in category-theoretic stuff, you'd call them quivers.
Ok, but what is a representation of a quiver? It's a fairly straightforward thing, actually:
Or, if you're more comfortable with more concrete descriptions,
For an example, let's take the \(\bullet\rightarrow\bullet\) quiver. A representation of this quiver is a pair of vector spaces and a linear map between them, or equivalently (after we choose a basis of the first vector space, and another basis of the second vector space), a representation is just some \(N\times M\) matrix (so, any matrix).
For another example, take the \(\bullet\style{display: inline-block; transform: rotate(-90deg)}{\circlearrowleft}\) quiver (one vertex, and one looping edge). For this quiver, we select just one vector space, and select an operator from this space to itself. Equivalently (after choosing a basis in this vector space), a representation of this quiver is just an \(N\times N\) matrix (i.e., any square matrix).
When talking about representations, the first thing one is interested in is classifying all possible representations. We've already did it in some sense in the previous section — we've determined that for two simple quivers, the representations are all possible matrices, or all possible square matrices. However, that doesn't really tell us much about how these are structured as representations.
There's one particularly simple operation we can do with representations of the same quiver: just add them. This doesn't have anything to do with usual matrix addition, though, so this operation is usually referred to as the direct sum. If we have two representations, — let's call them \(A\) and \(B\), — their direct sum \(A\oplus B\) is constructed like this:
In terms of coordinates,
The reason this is useful is that the \(A\) and \(B\) parts of the representation behave independently, so if we can decompose some representation into a sum of two smaller representations, then we can analyze them separately, which is typically much easier than analyzing the original representation as a whole.
Let's look at an example, with the same \(\bullet\rightarrow\bullet\) quiver. Recall that a representation of this quiver is just a linear map (a matrix) between two vector spaces. Take representation \(A\) to be \(\mathbb{R}^2\rightarrow\mathbb{R}^3\) with the matrix defined as \(\begin{pmatrix}1 & 2 \\ 3 & 4 \\ 5 & 6\end{pmatrix}\), and the representation \(B\) to be \(\mathbb{R}\rightarrow\mathbb{R}^2\) with the matrix \(\begin{pmatrix}-32 \\ -64\end{pmatrix}\). Then, the direct sum representation \(A\oplus B\) maps between vector spaces
\[ \mathbb{R}^2\oplus\mathbb{R}=\mathbb{R}^3 \quad\longrightarrow\quad \mathbb{R}^3\oplus\mathbb{R}^2=\mathbb{R}^5 \]
with the matrix
\[ \begin{pmatrix}1 & 2 & 0 \\ 3 & 4 & 0 \\ 5 & 6 & 0 \\ 0 & 0 & -32 \\ 0 & 0 & -64\end{pmatrix} \]
A representation that can be decomposed into a direct sum is called, well, decomposable. It's important to note that it doesn't mean that each matrix in the representation is block-diagonal; rather, that there exists a basis of each vector space involved such that the matrix (wrt this basis) will be block-diagonal. Remember the matrix vs operator distinction I stressed earlier? That's where it becomes important.
A representation that cannot be decomposed in such a way is called indecomposable. That's quite a mouthful, but it wasn't me who invented this term. It's a more or less trivial result that any representation can be decomposed into indecomposable ones: just keep decomposing while you can, and stop when you can't decompose more — at this point you have a direct sum of indecomposable representations (of course, in infinite dimensions you'd need to invoke Zorn's lemma).
So, to classify representations, it's enough to classify indecomposable ones, and that's exactly what we'll do for a bunch of simple-looking quivers.
The simplest possible quiver has...nothing. Zero vertices, zero edges. It has exactly one representation — the one that doesn't really specify any vector spaces or matrices. You might even object that this thing is a quiver at all!
The next simplest possible quiver has one vertex and no edges. Here it is in its full glory:
A representation of this quiver assigns a vector space to the only vertex and that's it, there are no edges to assign linear maps (aka matrices) to. Asking how a representation of this quiver decomposes as a direct sum is essentially asking when a single vector space can be decomposed as a direct sum.
Now, one of the first things one learns in a linear algebra course is that any vector space can be decomposed as a direct sum of one-dimensional spaces, which is just a fancy way of saying that any vector space has a basis! In terms of coordinates, direct sum of vector spaces corresponds to just concatenating the coordinate lists, so we could reformulate this as the fact that any list of numbers is a concatenation of single-element lists.
So, this quiver has only a single indecomposable representation, which assigns a 1-dimensional vector space (i.e. \(\mathbb{R}^1\)) to the only vertex of the quiver. Any representation (which is just a vector space) decomposes as a sum of copies of this representation (aka any vector space has a basis). The number of terms in this decomposition is simply the dimension of the vector space
Thus, the first few lectures of a linear algebra course are secretly about classifying representations of this quiver!
The next quiver we'll look at has two vertices and just one arrow between them:
As we've discussed before, a representation of this quiver is just any linear operator (i.e. any matrix), together with the source and destination vector spaces that this operator maps from/to. The question now is: up to a change of basis (both in the source and the destination vector spaces), what is the simplest way of representing a matrix in block-diagonal form?
Or, in terms of matrices, given our (not necessarily square!) matrix \(A\), can we find invertible square matrices \(P\) and \(Q\) such that \(P^{-1}AQ\) looks as simple as possible?
Indeed, we can! This is called \(LU\) decomposition (or better \(LDU\) decomposition), or Gauss elimination, or just the basic method of solving systems of linear equations!
Specifically, after applying the Gauss method, you've applied invertible transformations for rows/columns of your matrix (which is equivalent to multiplying it from the right/left by invertible square matrices — that's our change of basis), and you're left with a matrix that looks something like
\[ \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \]
i.e. the first \(K\) elements of the diagonal are ones, the rest of the diagonal is filled with zeros, and everything else is filled with zeroes as well.
In terms of basis vectors, this can be interpreted in the following way: we can choose a basis in the source vector space, and a basis in the destination vector space, such that
Paraphrasing this in terms of quiver representations, our quiver has exactly 3 indecomposable representations:
NB: the 0-dimensional space is a vector space that contains the zero vector and nothing else. In terms of coordinates, it corresponds to an empty list of coordinates. It's weird, but immensely useful in general context, much like the number 0.
Any representation of this quiver can be decomposed into a sum of copies of these 3 representations: one \(\mathbb{R}\rightarrow\mathbb{R}\) for each \(1\) on the diagonal (after Gauss elimination!), one \(\mathbb{R}\rightarrow 0\) for each zero column, and one \(0\rightarrow\mathbb{R}\) for each zero row.
So, the representation theory of this quiver boils down to the fact that Gauss elimination can decompose any matrix into a direct sum of these three forms above, which is what a typical linear algebra course secretly covers somewhere in the middle :)
The two quivers we've covered so far are the only ones in this post that have a finite number of indecomposable representations. This can be traced to Gabriel's theorem which states that the only such quivers are those whose underlying graph fits the ADE classification. Specifically, the \(\bullet\) and the \(\bullet\rightarrow\bullet\) quivers correspond to the \(A_1\) and \(A_2\) Dynkin diagrams.
You might think that a quiver with one vertex must be simpler than with two vertices, but there's a catch: since there's only one vertex, we have only one vector space, and we can only choose one basis! So we actually have less freedom in this case, and the emerging theory is more complicated.
Here's our quiver:
Recall that its representations are just square matrices, or operators acting on some vector space. Notice that in this case the source and destination spaces are forced to coincide, meaning we can only choose one basis to drive this matrix into some simpler form. In terms of matrices, we want to find an invertible \(P\) such that
\[ P^{-1}AP \]
has the simplest possible form. Notice that, unlike in the previous section, here that's the same matrix \(P\) on both sides!
This problem is famously solved using eigenvalues and the Jordan normal form: any square matrix can be turned into block-diagonal form with blocks that look like
\[ \begin{pmatrix} \lambda & 1 & 0 & 0 \\ 0 & \lambda & 1 & 0 \\ 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & \lambda \end{pmatrix} \]
where \(\lambda\) is an eigenvalue of our matrix.
Note that the eigenvalues can be complex, in which case the matrix and the basis vectors might be complex as well. The situation is a bit more complicated if we disallow this; e.g. we have to incorporate \(2\times 2\) rotation matrices corresponding to the complex eigenvalues.
For this quiver, the indecomposable representations are classified by the real number \(\lambda\) and a positive integer \(N\): such a representation is an \(N\times N\) Jordan block with \(\lambda\) on the diagonal. In particular, there's an infinite number of indecomposable representations!
So, once again, the representation theory of this quiver is something that's typically covered by a linear algebra course, probably somewhere in the second semester.
Now, this is something that goes beyond a typical linear algebra course. The quiver is
and its representations are just pairs of matrices between the same two vector spaces. We can choose the basis in the source vector space however we like, and the same goes for the destination space, but now we have two matrices that we want to decompose together, simultaneously. This makes the problem much harder!
But not wildly harder: the classification is known as the Kronecker Canonical Form. It's a bit involved, you can read here in more detail if you're interested. It typically classifies something called a matrix stencil, which is just a name for a linear matrix-valued polynomial in one variable, i.e. an expression like \(A+Bx\) where \(A\) and \(B\) are matrices (though there's often a minus sign \(A-Bx\) for historical reasons). However, this is more or less equivalent to just classifying pairs of matrices \((A,B)\) under simultaneously changing the source and destination bases, i.e. we want the two matrices
\[ P^{-1}AQ \quad P^{-1}BQ \]
to have the simplest possible form.
Although much less well-known, this stuff shows up routinely in control theory! And once again it can be seen as an instance of representation theory of quivers :)
This is the crown jewel of this post. Look at this absolute unit:
Like in the previous example, we have two matrices \(A\) and \(B\), but they are square, and they map from some vector space to the same space. We can only choose one basis, so we're interested in finding an invertible matrix \(P\) such that
\[ P^{-1}AP \quad P^{-1}BP \]
look as simple as possible.
This problem, and any problem that boils down to this problem, is called wild. It is believed that this problem is hopelessly difficult, to the point that a complete classification is so bizzarely complicated that it's mostly useless. In fact, it has been shown that such a classification would include the classification of all possible finite-dimensional algebras, which in my opinion is really, really wild.
So, quiver representations can represent things from the very basics of linear algebra to extremely advanced unsolvable problems. Kinda neat, isn't it? I hope you enjoyed it, too :)
I hate writing conclusion
sections. It feels like I'm in 7th grade, writing some boring essay. But it feels weirdly unfinished without it :/
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。