2
$\begingroup$

If a matrix can be constructed with simple bit-logic operations, is it also possible to find Eigenvalues with logic?

First I'll just say that my knowledge of logic is pretty much limited to programming experience, nor am I particularly seasoned with the computational limitations of analysing large matrices - this is an idea I'm coming across whilst pondering a QM system. I will, however, abstract as much of that as I can and get to the roots of my problem.

I am poking around at a large matrix (with dimension $2^{N} \times 2^{N}$). The matrix is made up of sums of kronecker products of identical pauli matrices (i.e. $X_3X_7 + 2Z_6Z_{10} + 3Y_{11}Y_{12} + ...$) corresponding to specific interactions between spin-1/2 particles at certain points on a finite Hexagonal lattice to explore edge effects. The basis, here, is the set of $2^N$ combinations of $N$ binary numbers, and $X_i$ refers to flipping the $i^\text{th}$ bit (from the right) of a state.

What I've been toying around with is making the construction of this matrix more efficient than using explicit tensor products. It is fairly evident that the matrix elements of $X_iX_j$ have a logical relationship by their mapping of state $|...a...b...\rangle$ to state $|...(\lnot a)...(\lnot b)...\rangle$ (where particles i and j are in initial state a and b respectively). In other words, $(X_iX_j)_{\alpha\beta} = (2^i \text{ XOR } \alpha == 2^j \text{ XOR } \beta)$, where of course only one such $\beta$ exists for each $\alpha$ ($\beta = \alpha \text{ XOR } 2^i \text{ XOR } 2^j$)

As such, the matrix can be constructed in comparatively little time for reasonable $N$, but obviously gets out of hand very quickly as $N$ increases.

There does, however, exist the (not so small) problem that such a matrix requires a lot of computing power to diagonalise - which is what I'm trying to do. However, the matrix itself is build entirely from strictly logical relationships - is it thus possible to implicitly find Eigenvalues of it, without realising it as a matrix in the first place?

I would immediately assume that the answer is no - and writing it out now makes me think it's a bit of a dumb question in the first place. However, I would be interested to see if anyone has any ideas.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I am poking around at a large matrix (with dimension 2^N×2^N). The matrix is made up of ... corresponding to specific interactions

is it thus possible to implicitly find Eigenvalues of it, without realising it as a matrix in the first place?

If you only care about a few of the eigenvalues then you don't have to realize the operator as a 2^N x 2^N matrix in the sense of explicitly creating a dense matrix in your computer memory. You can use some ARPACK functions instead. This would not be as efficient as having an explicit formula for the eigenvalues, but it would be more efficient than constructing the matrix explicitly.

You might have better luck asking on forums other than mathoverflow.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Arpack is a specific software for that task; more in general the theoretical tool that you need is Arnoldi methods. The short answer is: yes, it is possible (at least approximately) to solve linear systems and compute some specific eigenvalues (such as the ones with largest or smallest modulus) relying only on a function that computes the matrix product $v \mapsto Mv$. $\endgroup$
    – Federico Poloni
    Commented Nov 25, 2013 at 23:11
  • $\begingroup$ I'm currently using LAPACK, though I will look into ARPACK (as it seems to be useful for large, sparse matrices - though I figured LAPACK would be good enough due to the pretty basic structure of the matrix). Thanks Federico for enlightening me about Arnoldi methods (and the Lanczos iteration which I was lead to from the WIKI page). $\endgroup$
    – Jake
    Commented Nov 26, 2013 at 1:39
  • $\begingroup$ The structure of this matrix might make it simpler to construct the matrix powers by logic manipulation (rather than standard sparse multiplication), so I could find a speedup with a customised iterative method. I'm wondering if this kind of structure could lead to a direct approach to Eigenvalue calculation by logical operations rather than numerical approaches - for a general matrix of this kind. More general models of similar problems are pretty solid (otherwise condensed matter would be much less... fun), but something about the simplicity of this structure is almost screaming out to me. $\endgroup$
    – Jake
    Commented Nov 26, 2013 at 1:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .