Opened 6 years ago
Closed 6 years ago
#18645 closed enhancement (fixed)
Add some methods to CartanMatrix
Reported by:  jonathan.judge  Owned by:  jonathan.judge 

Priority:  major  Milestone:  sage6.8 
Component:  combinatorics  Keywords:  days65 
Cc:  bsalisbury1, tscrim, sagecombinat, bump, khlee, nthiery, vripoll, jipilab, jmichel  Merged in:  
Authors:  Jonathan Judge  Reviewers:  Ben Salisbury, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  dca9b68 (Commits)  Commit:  dca9b68d339238ef43c614dbd459ce41ee4c80d9 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket is to add the following methods to the CartanMatrix class in support of ticket #18000: is_indefinite()
, is_indecomposable()
, is_hyperbolic()
, principal_submatrices()
, and indecomposable_blocks()
.
Change History (22)
comment:1 Changed 6 years ago by
 Keywords days65 added
comment:2 Changed 6 years ago by
 Branch set to u/jonathan.judge/add_some_methods_to_cartanmatrix
comment:3 Changed 6 years ago by
 Commit set to 77f1bf6eced4549e4ea433d1904f273f4057baac
 Status changed from new to needs_review
comment:4 Changed 6 years ago by
 Cc bump khlee added
 Reviewers set to Ben Salisbury
Hi Jon,
Patch looks good, documentation looks good, and all tests passed.
 All tests passed!  Total time for all tests: 2285.1 seconds cpu time: 12380.9 seconds cumulative wall time: 17333.0 seconds
Some suggestions, though:
 Should the term
strict
inis_hyperbolic
be changed tocompact
to mesh with some current literature?
 Can you also add a method
is_Lorentzian
?
Best, Ben
comment:5 Changed 6 years ago by
 Commit changed from 77f1bf6eced4549e4ea433d1904f273f4057baac to bb250015dd24f433d84e92b28019b935359fb0a1
Branch pushed to git repo; I updated commit sha1. New commits:
bb25001  Added an is_lorentzian method, changed strict to compact for hyperbolic, and improved docs.

comment:6 Changed 6 years ago by
 Description modified (diff)
Some minor things:
 I think this logic
if compact: if not subg.is_finite(): return False else: if not subg.is_finite() and not subg.is_affine(): return False
could be rewritten asif not ( subg.is_finite() or (compact and subg.is_affine()) ): return False
(IMO usingor
reflects the definition better, but feel free to distribute thenot
).  I'd change
all([a.det() > 0 for a in self.principal_submatrices()])
intoall(a.det() > 0 for a in self.principal_submatrices())
as you don't need to create the intermediary list.  I'd replace
return comp_num == 0 or comp_num == 1
withreturn comp_num <= 1
.  The
INPUT:
block contents should not be indented.  Using Sage's
Set
is somewhat of a heavyhanded approach. So I'd make this change: from sage.sets.set import Set  iset = Set(range(self.ncols()));  ret = []  for l in iset.subsets(): + iset = range(self.ncols()) + from sage.misc.misc import powerset + ret = [] + for l in powerset(iset):
comment:7 Changed 6 years ago by
 Commit changed from bb250015dd24f433d84e92b28019b935359fb0a1 to 7e17029e1388141ba3cce2f160adc296afb18fcb
Branch pushed to git repo; I updated commit sha1. New commits:
7e17029  Cleaned up docs, removed some unnecessary intermediary lists, and added a method indecomposable_blocks().

comment:8 Changed 6 years ago by
Is there a generally accepted convention for deciding how to classify Cartan matrices whose blocks are of mixed type? For example, should a Cartan matrix with a finite block and an affine block be considered affine?
For now, the methods is_finite()
, is_affine()
, is_hyperbolic()
return false if the matrix is decomposable. Indecomposability is assumed in the classification in Kac's book (and Carter's), but I've seen other conventions (e.g. calling a Cartan matrix with multiple finite blocks a finite matrix).
With this in mind, I added the indecomposable_blocks()
method to make it easy for a user to check blocks individually for finiteness, affineness, and hyperbolicity.
comment:9 Changed 6 years ago by
 Cc nthiery added
IMO for finite, all types have to be finite because this gives you a finite root system (in particular, this makes all types contained in a finite type stay finite). Affine types I think is the trickiest, but I would say we'd want to keep the corank 1 property, so I would say no, decomposable types cannot be affine. For hyperbolic, I believe it follows from the definition that it has to be connected except for a single vertex disjoint from an affine type. However I'd make it uniform and say if it is decomposable, then it is not hyperbolic.
Nicolas, Dan, do either of you have thoughts on this?
comment:10 Changed 6 years ago by
 Cc vripoll jipilab jmichel added
This sounds reasonnable but this is going beyond my expertise zone. I am adding JeanPhilippe Labbé, Jean Michel and Vivien Ripoll in the loop, as they are likely to have some good insight on this matter (proper answer for is_affine
, is_hyperbolic
, ... for decomposable types).
comment:11 Changed 6 years ago by
Hi all,
Hmm. I also had thoughts about that recently when classifying finite and affine types. Here are some thoughts, suggestions, feel free to critize/ignore...
Have a look at #17798, there is a function "recognize_coxeter_type_from_matrix".
I usually use the following naming convention for Finite and Affine:
Finite types correspond to positive definite bilinear forms (reducible or not). For example, A_1 x A_1 should return True to "is_finite".
Affine types are not finite but the corresponding bilinear is semipositive definite. The group acts affinely on a Euclidean space. Note the "potentiality" here in the definition. Some may require that the dimension of the kernel of the bilinear be 1dimensional, so that an affine type should consist of only one affine component and possibly finite components.
I like to refer to finite and affine types as level 0 types (see below).
Hyperbolic (Bourbaki and Humphreys): The bilinear form is regular (trivial kernel) but has exactly one negative eigenvalue. Moreover, it is called compact if the fundamental cone is compact in the hyperbolic space. It is called finite volume if the volume of the cone is finite volume in the hyperbolic space.
+'s: this is classical nomenclature. 's: there are way more matrices that are regular and have exactly one negative eigenvalue.
The only reason I found in the litterature about naming these groups hyperbolic was that they are the ones that one can easily deal with (at the time). I believe this fact to be obsolete nowadays.
There is another naming convention which says that hyperbolic is exactly when the bilinear form is regular and has exactly one eigenvalue. This was adopted by Vinberg and Maxwell for example in the 70's and 80's. But this leads to confusion.
Another convention is when the bilinear form has exactly one negative eigenvalue and a nonzero kernel: weakly hyperbolic. IMHO, this "weakly" is misleading.
Have a look at Remark 2.2 of http://arxiv.org/abs/1310.8608 where there are references about this.
==============
To clarify all this, I like to use the notion of level and strictness that reveals a lot of structure.
A Coxeter matrix or Coxeter graph is of level 0 if it is finite or affine.
A Coxeter matrix or Coxeter graph is of "level =<r" if removing any set of r generators leaves a finite or affine type graph/matrix.
A Coxeter matrix or Coxeter graph is of level (exactly) r if it is not of level <=r1 but of level <=r.
A Coxeter matrix or Coxeter graph is strict if removing the r vertices always leaves a finite type.
The hyperbolic (compact and non compact) are the graphs of level 1. The compact hyperbolic types are exactly the strict level 1.
The level 2 graphs have signature (n1,1,0). This was proved by Maxwell and his enumeration was corrected in the above paper.
Instead of using hyperbolic I prefer to use the term Lorentzian to reflect the fact that the group acts not only on the hyperbolic space (which is part of a Lorentz space) but also on the outside of it. Note that the Lorentzian represent a potentiality. Lorentzian types are when the signature of the bilinear is (n1,1,0). When the kernel is nonzero, i.e. signature (m,1,k) I would use the term degenerate Lorentzian instead of weakly hyperbolic.
Sorry for the long text... Anyhow, this is more or less the picture as for Coxeter matrices and types.
As for the methods: very good to have them there!
comment:12 Changed 6 years ago by
It sounds like JeanPhilippe and I are in agreement that finite types include decomposable types whose pieces are all finite. This makes me also believe that we should have affine types include decomposable types whose pieces are all finite or affine. This would mean that the hyperbolic types are those of level 1 (and forced to be connected).
I'm also okay calling those Cartan types with a signature of (n1,1,0) as Lorentzian and those of (m,1,k) being degenerate Lorentzian. However I do think we should call the (strict) level 1 Lorentzian (resp., compact) hyperbolic to be as close with the classical literature as possible.
comment:13 Changed 6 years ago by
This sounds good to me. With respect to the code, I think the following changes to the most recent push should take care of things:
 change
is_finite()
to check if the matrix is positive definite;
 change
is_affine()
to check if the determinant is zero and if each indecomposable block is either finite or affine. With respect to checking affineness, I didn't find a matrix method for positive semidefiniteness. Is there a smarter way to do this than checking if the determinants of proper principal submatrices are positive?
Based on the discussion of levels and strictness above, I believe that the methods is_hyperbolic()
and is_lorentzian()
will yield correct results as they stand.
comment:14 Changed 6 years ago by
 Commit changed from 7e17029e1388141ba3cce2f160adc296afb18fcb to 8d06af9a2013822895f945e37cf7df0137b421ed
comment:15 Changed 6 years ago by
A couple of things:
 IMO
not self.det() == 0
would be better asself.det() != 0
.  Instead of
return len([x for x in self.eigenvalues() if x < 0]) == 1
, I would usesum(1 for x in M.eigenvalues() if x < 0)
since then we don't create the intermediate list (but this probably isn't really important since matrices we consider are usually "small").  I would do this import
from sage.misc.misc import powerset
at the module level. It makes the code run faster. (Sorry, I should have mentioned this earlier.)  I would cache the
is_*
methods since they actually seem to get called with some frequency (specificallyis_finite
).  I think your check for
is_hyperbolic
is overkill. You should instead iterate over the vertices and check the subgraph of everything except that vertex.
comment:16 Changed 6 years ago by
 Commit changed from 8d06af9a2013822895f945e37cf7df0137b421ed to 12895862c647d103d134c98ef18a5d8a934aeb5f
comment:17 followup: ↓ 18 Changed 6 years ago by
@tscrim: I think I've made all the changes you suggested.
A couple things that we should probably do (on another ticket?):
 add
is_hyperbolic
,is_lorentzian
andis_indefinite
methods to DynkinDiagram.  unify results here with those for reducible Cartan types. To see what I mean, note the difference between CM2 and CM3 below, where the matrices are the same, but where CM2 knows its CartanType while CM3 does not.
sage: CM1 = CartanMatrix("A2xA2") sage: CM1.is_finite() True sage: CM2 = CartanMatrix("A2~xA2") sage: CM2 [ 2 1 1 0 0] [1 2 1 0 0] [1 1 2 0 0] [ 0 0 0 2 1] [ 0 0 0 1 2] sage: CM2.is_finite() False sage: CM2.is_affine() False sage: CM3 = CartanMatrix([[2,1,1,0,0],[1,2,1,0,0],[1,1,2,0,0],[0,0,0,2,1],[0,0,0,1,2]]) sage: CM3.is_affine() True
comment:18 in reply to: ↑ 17 Changed 6 years ago by
 Reviewers changed from Ben Salisbury to Ben Salisbury, Travis Scrimshaw
Replying to jonathan.judge:
@tscrim: I think I've made all the changes you suggested.
Thanks. Although I would not cache principal_submatrices
as it returns a list of mutable matrices. I would change the output of indecomposable_blocks
to a tuple so that the output list cannot be changed. Once this is changed, you can set a positive review on my behalf.
A couple things that we should probably do (on another ticket?):
 add
is_hyperbolic
,is_lorentzian
andis_indefinite
methods to DynkinDiagram.
I'm happy doing this on another ticket as well. You might be interested in #15974 (which I have half forgotten about, half didn't have time for).
 unify results here with those for reducible Cartan types. To see what I mean, note the difference between CM2 and CM3 below, where the matrices are the same, but where CM2 knows its CartanType while CM3 does not.
sage: CM1 = CartanMatrix("A2xA2") sage: CM1.is_finite() True sage: CM2 = CartanMatrix("A2~xA2") sage: CM2 [ 2 1 1 0 0] [1 2 1 0 0] [1 1 2 0 0] [ 0 0 0 2 1] [ 0 0 0 1 2] sage: CM2.is_finite() False sage: CM2.is_affine() False sage: CM3 = CartanMatrix([[2,1,1,0,0],[1,2,1,0,0],[1,1,2,0,0],[0,0,0,2,1],[0,0,0,1,2]]) sage: CM3.is_affine() True
Yes, we do not have good type recognition for Cartan types. I think the better thing to do is to compare the Dynkin diagrams (as digraphs) and do type recognition and relabeling that way. However this is definitely a separate ticket.
Also, please add your real name as the author.
comment:19 Changed 6 years ago by
 Commit changed from 12895862c647d103d134c98ef18a5d8a934aeb5f to dca9b68d339238ef43c614dbd459ce41ee4c80d9
Branch pushed to git repo; I updated commit sha1. New commits:
dca9b68  Removed caching on principal_submatrices and changed indecomposable_blocks to return a tuple instead of a list.

comment:20 Changed 6 years ago by
 Description modified (diff)
comment:22 Changed 6 years ago by
 Branch changed from u/jonathan.judge/add_some_methods_to_cartanmatrix to dca9b68d339238ef43c614dbd459ce41ee4c80d9
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Added methods is_indefinite(), is_hyperbolic(), is_indecomposable(), and principal_submatrices() to the class CartanMatrix