safelix
commented
1 year ago Hi Rory,
Thank you for your interest in my bachelor thesis! I'm not too familiar with the problem/code anymore and would need to spend some time to properly answer your question. At the time I was also mostly concerned with integer/binary matrices (coming from graphs), which generally resulted in a rational decompositions. I can't recall if it ever occurred to me to consider solutions under a finite field assumption, but this would indeed be interesting!
I think that all/most underlying polynomial manipulation methods (core/polynomial.{h|c}pp) and algorithms (core/algorithms.{h|c}pp) are implemented as header-only, templated with a scalar type, and are only materialized at compile time. This means that it should theoretically be possible to instantiate them with binary/booleans instead of rational numbers quite easily.
The JDec class (core/jordanchevalley.{h|c}pp) is not templated and takes a double matrix (or a memory map as a C array) as input which is then cast to a rational. Here, the 6 steps to compute D, N are performed on rational matrices/polynomials, instantiating the templated low-level methods/algorithms as explained above. This would need to be adapted for finite fields, but shouldn't require too much effort from an implementation point of view.
Algorithmically, the largest problem I see, is the first step: the computation of the characteristic polynomial of binary matrices, which I approximated using La Budde's method with a specifiable floating point precision. Since for binary matrices, the characteristic polynomial has generally integer coefficients, I could recover the exact result in these cases again. I don't know how this would behave under a finite field assumption or if it would be computable (exponential growth might be a problem), but I could imagine that such a binary characteristic polynomial exists. If you manage to do that, a second problem might occur in taking derivatives of the binary polynomials under a finite field assumption, which is required to get the minimal polynomial and perform the Chevalley iteration. You might want to consider the algorithm section in my thesis.
TLDR; I'm not sure if the decomposition really exists under a finite field assumption. But if it exists, the code should be extendable with not too much effort.
If you have any follow-up questions or new findings, I would be interested to discuss them with you:)
Cheers, Felix
Hello,
Thank you for the implementation, I found it useful. I am wondering if the implementation could be adapted to work in finite fields? In particular I am interested in JC decompositions of binary matrices, e.g. those used in cryptography or random number generation.
If I'm not mistaken, the decomposition also exists and is unique in these cases.
Thanks