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: sage-6.8
Component: combinatorics Keywords: days65
Cc: bsalisbury1, tscrim, sage-combinat, 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 jonathan.judge)

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 jonathan.judge

  • Keywords days65 added

comment:2 Changed 6 years ago by jonathan.judge

  • Branch set to u/jonathan.judge/add_some_methods_to_cartanmatrix

comment:3 Changed 6 years ago by jonathan.judge

  • Commit set to 77f1bf6eced4549e4ea433d1904f273f4057baac
  • Status changed from new to needs_review

New commits:

77f1bf6Added methods is_indefinite(), is_hyperbolic(), is_indecomposable(), and principal_submatrices() to the class CartanMatrix

comment:4 Changed 6 years ago by bsalisbury1

  • 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 in is_hyperbolic be changed to compact to mesh with some current literature?
  • Can you also add a method is_Lorentzian?

Best, Ben

comment:5 Changed 6 years ago by git

  • Commit changed from 77f1bf6eced4549e4ea433d1904f273f4057baac to bb250015dd24f433d84e92b28019b935359fb0a1

Branch pushed to git repo; I updated commit sha1. New commits:

bb25001Added an is_lorentzian method, changed strict to compact for hyperbolic, and improved docs.

comment:6 Changed 6 years ago by tscrim

  • 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 as
    if not ( subg.is_finite() or (compact and subg.is_affine()) ):
        return False
    
    (IMO using or reflects the definition better, but feel free to distribute the not).
  • I'd change all([a.det() > 0 for a in self.principal_submatrices()]) into all(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 with return 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 git

  • Commit changed from bb250015dd24f433d84e92b28019b935359fb0a1 to 7e17029e1388141ba3cce2f160adc296afb18fcb

Branch pushed to git repo; I updated commit sha1. New commits:

7e17029Cleaned up docs, removed some unnecessary intermediary lists, and added a method indecomposable_blocks().

comment:8 Changed 6 years ago by jonathan.judge

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 tscrim

  • 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 nthiery

  • Cc vripoll jipilab jmichel added

This sounds reasonnable but this is going beyond my expertise zone. I am adding Jean-Philippe 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 jipilab

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 semi-positive 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 1-dimensional, 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 non-zero 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 <=r-1 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 (n-1,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 (n-1,1,0). When the kernel is non-zero, 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 tscrim

It sounds like Jean-Philippe 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 (n-1,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 jonathan.judge

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 affine-ness, I didn't find a matrix method for positive semi-definiteness. 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 git

  • Commit changed from 7e17029e1388141ba3cce2f160adc296afb18fcb to 8d06af9a2013822895f945e37cf7df0137b421ed

Branch pushed to git repo; I updated commit sha1. New commits:

3289b28Some updates to is_finite and is_affine
8d06af9Merge branch 'develop' into t/18645/add_some_methods_to_cartanmatrix

comment:15 Changed 6 years ago by tscrim

A couple of things:

  • IMO not self.det() == 0 would be better as self.det() != 0.
  • Instead of return len([x for x in self.eigenvalues() if x < 0]) == 1, I would use sum(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 (specifically is_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 git

  • Commit changed from 8d06af9a2013822895f945e37cf7df0137b421ed to 12895862c647d103d134c98ef18a5d8a934aeb5f

Branch pushed to git repo; I updated commit sha1. New commits:

70e492efixing a typo in boolean condition in is_affine
0e20543Merge branch 'develop' into t/18645/add_some_methods_to_cartanmatrix
1289586More cleanup and optimizations.

comment:17 follow-up: Changed 6 years ago by jonathan.judge

@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 and is_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 tscrim

  • 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 and is_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 git

  • Commit changed from 12895862c647d103d134c98ef18a5d8a934aeb5f to dca9b68d339238ef43c614dbd459ce41ee4c80d9

Branch pushed to git repo; I updated commit sha1. New commits:

dca9b68Removed caching on principal_submatrices and changed indecomposable_blocks to return a tuple instead of a list.

comment:20 Changed 6 years ago by jonathan.judge

  • Authors set to Jonathan Judge
  • Description modified (diff)

comment:21 Changed 6 years ago by tscrim

  • Status changed from needs_review to positive_review

Thanks!

comment:22 Changed 6 years ago by vbraun

  • Branch changed from u/jonathan.judge/add_some_methods_to_cartanmatrix to dca9b68d339238ef43c614dbd459ce41ee4c80d9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.