• Register
PhysicsOverflow is a next-generation academic platform for physicists and astronomers, including a community peer review system and a postgraduate-level discussion forum analogous to MathOverflow.

Welcome to PhysicsOverflow! PhysicsOverflow is an open platform for community peer review and graduate-level Physics discussion.

Please help promote PhysicsOverflow ads elsewhere if you like it.


New printer friendly PO pages!

Migration to Bielefeld University was successful!

Please vote for this year's PhysicsOverflow ads!

Please do help out in categorising submissions. Submit a paper to PhysicsOverflow!

... see more

Tools for paper authors

Submit paper
Claim Paper Authorship

Tools for SE users

Search User
Reclaim SE Account
Request Account Merger
Nativise imported posts
Claim post (deleted users)
Import SE post

Users whose questions have been imported from Physics Stack Exchange, Theoretical Physics Stack Exchange, or any other Stack Exchange site are kindly requested to reclaim their account and not to register as a new user.

Public \(\beta\) tools

Report a bug with a feature
Request a new functionality
404 page design
Send feedback


(propose a free ad)

Site Statistics

145 submissions , 122 unreviewed
3,928 questions , 1,396 unanswered
4,846 answers , 20,597 comments
1,470 users with positive rep
501 active unimported users
More ...

Simplify K-matrix

+ 3 like - 0 dislike

2+1D Abelian topologically ordered states are believed to be described by multicomponent $U(1)$ Chern-Simons theories, with Lagrangian
\mathcal{L}=\frac{K_{IJ}}{4\pi}\epsilon^{\mu\nu\lambda}a_\mu^I\partial_\nu a_\lambda^J-\frac{1}{2\pi}t_I\epsilon^{\mu\nu\lambda}A_\mu\partial_\nu a_\lambda^I
where $K$ is a invertible symmetric matrix with integer entries, and $t$ is a vector with integer entries.

Different $K$-matrices differing by a matrix in $GL(N,\mathbb{Z})$ are equivalent, namely, if $K_1$ and $K_2$ satisfy
where $W$ is a matrix with integer entries and unit determinant, then $K_1$ and $K_2$ describe the same physics. 

Sometimes it is useful to simplify a $K$-matrix by using an appropriate $W$ matrix, i.e. $K\rightarrow W^TKW$, so that the resulting new $K$ is block diagonal. I do not know any general procedure of doing this, and I appreciate if anyone can help.

If a general procedure is too hard, it is also helpful just to show how to find the appropriate $W$ that simplifies the following specific $K$-matrix:

\(\begin{equation} K= \left( \begin{array}{cccc} 2&-1&0&0\\ -1&0&2&1\\ 0&2&0&0\\ 0&1&0&1 \end{array} \right) \end{equation}\)

asked Apr 21, 2016 in Theoretical Physics by Mr. Gentleman (255 points) [ revision history ]
edited Apr 26, 2016 by Mr. Gentleman

Every matrix can be transformed by an equivalence transformation of the kind you state to bring it into diagonal form, e.g., by a change of basis to an orthogonal eigensystem of $K$. A corrsponding change of the annihilation operators then simplifies that action wiithout changing the physics.

So is there any general procedure of doing it?

Always if you don't insist that the new $K$ is integral, too. (I hadn't noticed the integrality constraint when I wrote my first comment.) Integer congruence transformation to diagonal or block diagonal form do not always exist, only if the lattice defined by $K$ splits into a direct sum of smaller lattices.

Could you please give a reference where the action appears, so that I can understand the origin of the integrality condition. Is $K$ known to be positive definite, or known to be indefinite?

The origin of the integrality is charge quantization, or more formally, the compactness of the gauge field. Being compact, we require the partition function of the Chern-Simons theory to be invariant under $a\rightarrow a+2\pi$, and it turns out that only if the matrix $K$ is integral will this be satisfied. There is no positivity condition on $K$ though. For references, Xiao-Gang Wen's book Quantum Field Theory of Many-Body Systems may be good. Thank you.

In the positive definite case, the problem of simplifying $K$ is the problem of finding a normal form for the Gram matrix of an integral lattice. This is a well-studied (though in high dimensions very difficult) problem in number thoery. I suggest that you look into the book Sphere Packings, Lattices and Groups by Conway and Sloane. I'll write a proper answer after having looked more at the context of your question - this may take a while. 

Many thanks!

3 Answers

+ 4 like - 0 dislike

Let $K$ be a symmetric $n\times n$ matrix with integer coefficients. The additive abelian group of integer vectors of size $n$ gets a lattice structure by defining the (not necessarily definite) integral inner product $(x,y):=x^TKy$. It is conventional to call the integer $(x,x)$ the norm of $x$ (rather than its square root, as in Hilbert spaces). A standard referecne for lattices is the book Sphere Packings, Lattices and Groups by Conway and Sloane. (It covers the definite case only. For the indefinite case see, e.g., the book An introduction to the theory of numbers by Cassels.

If $K$ is positive semidefinite, one has a Euclidean lattice in which all vectors have nonnegative integral norm $(x,x)$. The vectors of zero norm are just the integral null vectors of $K$; they form a subgroup that can be factored out, leaving a definite lattice of smaller dimensions where all nonzero points have positive norm.

In a definite lattice, there are only finitely many lattice points of a given norm. coming in antipodal pairs that can be found by a complete enumeration procedure (typically an application of the LLL algorithm followed by Schnorr-Euchner search, or more advanced variations). The collection of all vectors of small norm define a graph whose edges are labelled by the nonzero inner products. Lattice isomorphism (corresponding to equivalence of the $K$ under $GL(n,Z)$) can be tested efficiently by testing these labelled graphs for isomorphism, e.g., using the graph isomorphism package nauty. (Of course one first checks whether the determinant of $K$, which is an invariant is the same.) This makes checking for decomposability a finite procedure (recursive in the dimension). It is not very practical in higher dimensions unless the lattice decomposes into a large number of lattices generated by vectors of norm 1 and 2. However, if some of these graphs are disconnected they suggest decompositions that can be used in a heuristic fashion.

In an indefinite lattice (i.e., when $K$ is indefinite) there are always vectors of norm zero that are not null vectors of $K$. The norm zero vectors no longer form a subgroup. Classification and isomorphism testing is instead done by working modulo various primes, giving genera. Again one has a finite procedure. 

To solve the decomposition problem posed for given $K$, one shouldn't need to do a full classification of all lattices of dimension $n$. But I don't know a simpler systematic procedure that is guaranteed to work in general. In higher dimensions most lattices are indecomposable, though there are no simple criteria for indecomposability. The key to decomposition is to transform the basis in such a way that a subset of the basis vectors becomes orthogonal to the remaining ones, and to repeat this recursively as long as feasible.

This gives rise to the following heuristics that works well for the specific matrix given. One transforms the basis so that it contains points $x$ of absolutely small nonzero norm (reflected by corresponding diagonal entries) and subtracts integral multiples of $x$ from the other basis vectors in order to make the absolute values of the inner products as small as possible. [Finding these short vectors is often trivial by inspection, but if the original diagonal entries are large lattice reduction methods (of which LLL is the simplest) must be used to find them or to show their nonexistence.] This is repeated as long as the sum of absolute values of the off-diagonal entries decreases. If a diagonal entry is $\pm1$ one can make in this way all off-diagonal entries zero and obtains a 1-dimensional sublattice that decomposes the given lattice. (For absolutely larger diagonal entries there is no such guarantee, but the case of norm $\pm2$ is usually tractable, too, since one can use the structure theory of root lattices to handle the sublattice generated by norm 2 vectors.)

In the specific (indefinite) case given, the fourth unit vector $e^4$ has norm 1, and transforming the off-diagonals in the 4th column to zero produces the reduced matrix {2,-1,0,-1,-1,2;0,2,0]. Now the second unit vector has norm -1, and doing the same with column 2 gives the reduced matrix [3 -2;-2,4]. This matrix is definite, and one can enumerate all vectors of norm $\le 4$ to check that it is indecomposable. One can still improve the basis a little bit , replacing [3 -2;-2,4] by [3 1;1 3].

Collecting the transformations done one finds a unimodular matrix that transforms  $K$ into the direct sum of [3,-2;-2,,4], [-1], and [1]. Or  [3 1;1 3], [-1], and [1].

answered Apr 26, 2016 by Arnold Neumaier (12,355 points) [ revision history ]
edited Apr 27, 2016 by Arnold Neumaier

Thank you for your detailed answer. But it seems the simplified matrix you gave has a different determinant compared to the original one... Can you write down the $W$-matrix explicitly?

@Mr.Gentleman: Sorry, silly mistake. I corrected my calculation. The determinant is now always $-8$. An explicit $W$ is given in the answer by Meng if you apply a column permutation interchanging coordinates 2 and 3.

+ 3 like - 0 dislike

There is no way to do this in general. Here is some background http://www.maths.ed.ac.uk/~aar/papers/conslo.pdf

Interestingly, there is a classification of *indefinite* bilinear forms over Z.

answered Apr 23, 2016 by Ryan Thorngren (1,605 points) [ no revision ]

''No way'' is too much said. Every single dimension is decidable (with a finite number of equivalence classes). It just gets harder with the dimension.

Is that a theorem? Maybe eventually it gets undecidable.

Yes, it is  theorem. The absolute value of the determinant is an invariant. Using LLL reduction one can always find (for any fixed dimension and determinant) an explicit basis of bounded length. Then the number of possible Gram matrices in such a reduced basis is finite. Since one can decide lattice isomorphism, it follows that one can figure out the precise number of equivalence classes for each dimension and determinant.


Thank you for the comments. Because of my lack of background, I think I will have to learn these. However, at this moment I have a particular problem with $K=(2,-1,0,0;-1,0,2,1;0,2,0,0;0,1,0,1)$ (the comma separates elements in the same row and the semicolon separates different rows), can anyone help me block diagonalize it?

@Mr.Gentleman: Please add this information to your question, and I'll answer it.

@Arnold Neumaier: updated, thank you!

+ 3 like - 0 dislike

Let $$ W=\left(
 1 & 0 & 1 & 0 \\
 -1 & 0 & 1 & 1 \\
 1 & -1 & 0 & -1 \\
 -1 & 1 & 1 & 1 \\
\right), $$


$$ W^T K W=\left(\begin{array}{cccc}
 3 & 0 & 1 & 0 \\
 0 & 1 & 0 & 0 \\
 1 & 0 & 3 & 0 \\
 0 & 0 & 0 & -1 \\
\end{array}\right) $$

W is found by trial and error.

answered Apr 27, 2016 by Meng (550 points) [ no revision ]

How to try and err? There are infinitely many possibilities for $W$ and only a few work. So what was your heuristics to find $W$?

Your answer

Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead.
To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL.
Please consult the FAQ for as to how to format your post.
This is the answer box; if you want to write a comment instead, please use the 'add comment' button.
Live preview (may slow down editor)   Preview
Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:
Then drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds).
To avoid this verification in future, please log in or register.

user contributions licensed under cc by-sa 3.0 with attribution required

Your rights