Matrix Decompositions: Iwasawa, Cartan, Bruhat-Iwahori, TSB, Bruhat

[333767a0-8bb0-4499-a032-33e52572d678]

In this ticket, I add implementations for the following decompositions:

• Decompositions for square matrices over non-archimedean local fields:

  1. Iwasawa.
  2. Cartan.
  3. Bruhat-Iwahori.
  4. TSB (T - invertible upper-triangular, S - permutation matrix (possibly with some zero-rows), B - iwahori matrix).

• Bruhat decomposition for square matrices over any field.

Notes and Issues:

1. In the above decompositions, Some of the returned matrices could be defined over the integer-ring of the field, but I did not coerce them into the integer-ring, because of the bug described at: #29931.
2. To prevent any of the above decompositions from making changes to the original matrix, I used the fact that the matrix_over_field method returns a deep copy of the original matrix (even when the original is already defined over a field).
3. A point for consideration: as padics and formal laurent-series over finite fields are both non-archimedean local fields, I needed to make sure that the implemented methods work for both. Having a more uniform API for padics and laurent-series could be helpful in avoiding awkward nested functions that fit different implementations for each type. For example, for getting the unit-part of an element, I had to use the unit_part method for padics, and valuation_zero_part for laurent.

Depends on #30432

CC: @oriparzan @tscrim

Component: linear algebra

Keywords: laurent, decomposition, iwasawa, bruhat, bruhat-iwahori, TSB, cartan

Author: Noa Viner

Branch/Commit: u/caruso/matrix_decompositionsiwasawacartan__bruhat_iwahoritsbbruhat @ 5aaf4d7

Issue created by migration from https://trac.sagemath.org/ticket/30690

[333767a0-8bb0-4499-a032-33e52572d678]

Branch: u/gh-n-vi/matrix_decompositionsiwasawacartan__bruhat_iwahoritsbbruhat

[333767a0-8bb0-4499-a032-33e52572d678]

Commit: 68789cc

[333767a0-8bb0-4499-a032-33e52572d678]

New commits:

514cec9	insert decompositions
68789cc	Integrating in Matrix class.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

47ae46b

Fixing indentation of doctests and skipping some doctests

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 68789cc to 47ae46b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 47ae46b to 35435f7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

35435f7

Continue fixing indentation of doctests.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8b587e7

Doctests: Changing enumerated lists from numbers to big letters

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 35435f7 to 8b587e7

[mkoeppe]

comment:8

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:9

Setting a new milestone for this ticket based on a cursory review.

[mkoeppe]

comment:10

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8b587e7 to 0d4bec6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

4c7001e	Merge branch 'develop' into t/30690/matrix_decompositions__iwasawa__cartan__bruhat_iwahori__tsb__bruhat
0d4bec6	adding eq_zero for relaxed padics

[tscrim]

comment:12

This would be a good feature to have. Some very quick comments:

• Remove the ... at the end of the docstrings.
• I think you are forgetting that a square matrix M is generally not something equal to M = A² for some other matrix A. It would be good to change the doc for this method.
• Why is _iwasawa_normalized_form a @staticmethod`? It is most natural as a normal method IMO.
• Remove the period/full-stop at the end of every INPUT: (short) bullet point.
• _matrix_func_that_switches_cols_and_nullifies should just be a function in the file that is called directly, and preferably has a shorter name.
• `iwasawa` -> :meth:`iwasawa()` I think.
• Iwasawa should be capitalized in the documentation.
• ``self``[``r``,``c``]!=0 -> ``self[r,c] != 0``
• Remove the space before each :: as there should be a : in the docstrings.
• There are lots of things that should be code formatted; e.g., in min_valuation_in_row.
• In choose_min_valuation_elem, change TESTS:: -> TESTS:.
• Don't abbreviate names, especially for just 3 characters; e.g., choose_min_valuation_elem[ent] (min is fine though).
• I am sure many of these comments have similar analogs, such as capitalizing Bruhat. However, I have not yet skimmed everything yet.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0d4bec6 to 6ac07aa

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

627d590	removing three dots at the end of docstrings + removing periods at the end of each input bullet
44c1238	adding :meth: before mentioning names of methods in the documentation
2d21362	Capitalizing names in the documentation (Iwasawa, Cartan, Bruhat, Bruhat-Iwahori, Iwahori)
03f1f0c	Changing documentation of self[index1,index2] to self[index1,index2]
1f13be3	remove space before each ::
b7aa3b1	Adding some documentation to the code
9b071fc	Replacing TESTS:: by TESTS:
6ac07aa	Replacing choose_min_valuation_elem by choose_min_valuation_element

[333767a0-8bb0-4499-a032-33e52572d678]

comment:14

Hi, thanks for the review.

I changed everything you suggested, apart from some comments which I did not understand:

1. Regarding the square matrix - where did I assume that it is the square of another matrix?
2. I thought _iwasawa_normalized_form should by static because it takes 2 matrices that are already an Iwasawa decomposition of another matrix, and normalizes them. If not static, then which of the matrices in the decomposition should be the self in this method?
3. What do you mean by: "_matrix_func_that_switches_cols_and_nullifies should just be a function in the file that is called directly"? Also, I have several similar functions so I didn't manage to come up with a shorter name, I hope this is O.K..
4. I replaced elem with element. Should I also replace func and col that appear in other methods' names, or are they fine, like min? Thank you very much.

[tscrim]

comment:15

Replying to @n-vi:

1. Regarding the square matrix - where did I assume that it is the square of another matrix?

In _is_square_over_non_archimedean_local_field, what does "square" mean? If it means an n x n matrix, we already have a very simple test and method for that.

2. I thought _iwasawa_normalized_form should by static because it takes 2 matrices that are already an Iwasawa decomposition of another matrix, and normalizes them. If not static, then which of the matrices in the decomposition should be the self in this method?

Then it should be a separate function. There is no need to add it to the matrix class itself. Continuing this line of reasoning, it would be best to be in a separate file, in part to also not lengthen matrix2.pyx even more. Also the name is a bit misleading as it suggests it builds the (normalized) Iwasawa decomposition. I would call it _normalize_iwasawa_decomposition().

3. What do you mean by: "_matrix_func_that_switches_cols_and_nullifies should just be a function in the file that is called directly"?

Exactly as I said, it simply is returning a function f it creates and this method is called exactly once in the code. Just simply use that function f in the one place it is called. This is a convoluted piece of code that can be simplified.

4. I replaced elem with element. Should I also replace func and col that appear in other methods' names, or are they fine, like min?

col is fine. As per my previous comment, you should be removing all of the methods with func.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3e0f7c7	Checking squareness of matrix separately from whether it is over a non-archimedean local field.
ca169d4	Changing name of function: _iwasawa_normalized_form to _normalize_iwasawa_decomposition

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6ac07aa to ca169d4

[333767a0-8bb0-4499-a032-33e52572d678]

comment:17

Hi Julian, thanks again.

1. By using the term "square" I indeed referred to a n*n matrix, but I understand that it was misleading so I separated the squareness check from this method, and used the existing is_square method for that, as you suggested.
2. As for _iwasawa_normalized_form, I changed the name as you suggested. Can you please explain, though, in what file I should put this function? I don't know what the conventions are in sage.
3. Regarding the _matrix_func.. methods, I have a slight problem with inserting them into the code directly (rather then as different methods). To begin with, there are 3 of them, and one (_matrix_func_that_nullifies_part_of_col) is called 3 times from different parts of the code. Also, to me the code feels much more understandable as it is, rather than as it would be after inserting those methods into the code directly (the code is already rather complicated in its own right). Perhaps you could have a look and tell me your opinion..

---

New commits:

3e0f7c7	Checking squareness of matrix separately from whether it is over a non-archimedean local field.
ca169d4	Changing name of function: _iwasawa_normalized_form to _normalize_iwasawa_decomposition

[xcaruso]

comment:18

I agree that it is nice to have all these decompositions but I think that several of them are already available under different names:

• the Iwasawa decomposition is given by the Hermite normal form (see ticket #23486 I've just updated today)
• the Cartan decomposition is given by the Smith normal form
• the Bruhat decomposition can be deduced from the echelon form and the position of the pivots.

Maybe you should consider taking advantage of these normal forms to shorten your code and make it easier to review.

Also, I'm not very enthousiastic to have so many underscore helper methods. IHMO, it's better to turn them into functions and put them outside the class.

[saraedum]

comment:19

Also, I'm not very enthousiastic to have so many underscore helper methods. IHMO, it's better to turn them into functions and put them outside the class.

Yes, there are quite a lot of these. It's a matter of style but I think it's fine like this. Some of them could probably be nested def in the implementation. If a helper can be clearly associated to a function, it's maybe a good idea to prefix them so it's clear without reading the code, i.e., if def _do_something() is a helper of def factor(), then it's often nice to call it def _factor_do_something().

[saraedum]

comment:20

I cloned the changeset here to https://gitlab.com/sagemath/sage/-/merge_requests/56 where it's hopefully much easier to review this.

[saraedum]

comment:21

(This created a duplicate of this ticket at https://github.com/sagemath/sage-prod/issues/33404 that we can probably ignore. Or we close this one here in favor of the latter if we agree that working on this on GitLab is more convenient at this stage.)

[xcaruso]

Changed branch from u/gh-n-vi/matrix_decompositionsiwasawacartan__bruhat_iwahoritsbbruhat to u/caruso/matrix_decompositionsiwasawacartan__bruhat_iwahoritsbbruhat

[333767a0-8bb0-4499-a032-33e52572d678]

Changed branch from u/caruso/matrix_decompositionsiwasawacartan__bruhat_iwahoritsbbruhat to u/gh-n-vi/matrix_decompositionsiwasawacartan__bruhat_iwahoritsbbruhat

[333767a0-8bb0-4499-a032-33e52572d678]

Changed branch from u/gh-n-vi/matrix_decompositionsiwasawacartan__bruhat_iwahoritsbbruhat to u/caruso/matrix_decompositionsiwasawacartan__bruhat_iwahoritsbbruhat

[333767a0-8bb0-4499-a032-33e52572d678]

Changed commit from ca169d4 to 5aaf4d7

[333767a0-8bb0-4499-a032-33e52572d678]

comment:24

Hi, thank you for the comments.

Regarding the helper methods: If you think it best, I can gladly convert them into functions in a different file (in that case I will need some help understanding where to put them). I also tried to prefix the names as suggested by Julian, but didn't find a way of doing so without getting really long names. However, if you have any ideas in that direction I will be happy to hear.

[333767a0-8bb0-4499-a032-33e52572d678]

comment:25

Replying to @xcaruso:

I agree that it is nice to have all these decompositions but I think that several of them are already available under different names:

• the Iwasawa decomposition is given by the Hermite normal form (see ticket #23486 I've just updated today)
• the Cartan decomposition is given by the Smith normal form
• the Bruhat decomposition can be deduced from the echelon form and the position of the pivots.

Continuing our discussion, here are some differences between Iwasawa and Cartan to the Hermite-Normal-Form and Smith-Normal-Form:

1. The HNF and SNF implementations are more generic in the following senses:

   • HNF and SNF receive also non-square matrices (whereas Iwasawa and Cartan receive only square ones).
   • If I understand correctly, Iwasawa and Cartan are compatible with the specific case of integral=True.
   • Iwasawa and Cartan work only for matrices over fields (or rings with fraction fields) which are non archemidean local (p-adics or laurent-series rings), whereas at least in the documentation of SNF, it is said that it works for any local field (not necessarily non-archemidean).

2. Optional arguments:

   • In HNF and SNF you can control the accuracy of the matrices in the decomposition and you can choose whether to get the transformation matrices or rather to only get the 'main' matrix in the decomposition.
   • In Iwasawa and Cartan you can get an indication to whether there was a numerical-inaccuracy issue that caused some of the output matrices to become singular rather than invertible.

3. There are some differences in the requirements for the output matrices. For the record, here is a detailed description of the output in Iwasawa and Cartan, for an input matrix A:

   • Iwasawa returns matrices T,K such that A=T*K : K is invertible over the integer ring and T is upper triangular (note that in this implementation the transformation matrix is on the right). In the normalized case T has powers of the uniformizer on diagonal, and on the right-hand side the elements are truncated starting from the valuation of the diagonal-element in that row.

• Cartan returns matrices K1,D,K2 such that A=K1DK2 : K1,K2 are invertible over the integer ring, and D is diagonal with ascending powers of the uniformizer on diagonal (or zeros, which are considered as infinity powers).

As for Bruhat - I am not sure yet how to deduce it from the echeclon form (bearing in mind that I need to have all 3 matrices in the decomposition, rather than only the permutation matrix) but I can think about it.

[tscrim]

comment:26

The Bruhat decomposition (for GL_n) is just the LU decomposition with the permutation matrix needed for moving the pivots being the Weyl/permutation group element defining the cell/orbit you are in.

I strongly disagree with you about the readability of _matrix_func_that_nullifies_part_of_col and like methods. They add useless extra layers and complexity. In this case, it is a function that simply returns a function and does nothing else.

matrix2.pyx is already very long and IMO all @staticmethods definitely should be in a separate file as they are not for matrices in general but a very specific input.

[333767a0-8bb0-4499-a032-33e52572d678]

comment:27

Hi, thank you for the comments!

Regarding the Bruhat decomposition - I think there might be some confusion in the names of the decompositions. The Bruhat decomposition I am talking about for a matrix A, is A=T1ST2, such that S is a permutation matrix and T1,T2 are invertible upper triangular. From our discussion at: https://sagemath.zulipchat.com/#narrow/stream/271072-padics/topic/matrix.20decompositions/near/273104719, it didn't seem to be deducible from echelon. Do you think differently?

As for the helper functions, I understand now that they should have been put somewhere else, and I am willing to change this - I would probably need some guidance as to where to put them though.

By the way, I am not sure whether this ticket is still followed by the others. Perhaps it would be best to move our discussion to the gitlab branch: https://gitlab.com/sagemath/sage/-/merge_requests/56.

Thank you!

[tscrim]

comment:28

Let's actually keep the discussion here please. I don't want to fragment things even further.

You can easily get the upper triangular case by acting by the longest element first (which simply reverses the rows), and then undoing that for the L matrix by conjugation, making it into an upper triangular matrix, and also multiplying it to the permutation matrix. Basically any other form of Borel versus opposite Borel is equivalent by some w0 multiplication. It is a simple exercise.

[xcaruso]

comment:29

Replying to @tscrim:

You can easily get the upper triangular case by acting by the longest element first (which simply reverses the rows), and then undoing that for the L matrix by conjugation, making it into an upper triangular matrix, and also multiplying it to the permutation matrix. Basically any other form of Borel versus opposite Borel is equivalent by some w0 multiplication. It is a simple exercise.

Could you please do the exercise for us? I tried yesterday but didn't manage to.

Besides, this paper https://hal.archives-ouvertes.fr/hal-01251223v2/document seems to say that what we need to compute a Bruhat decomposition is a "PLUQ decomposition revealing the rank profile"; a classical PLU decomposition is not enough.

Another hint supporting that Bruhat is a bit different from PLU is that the permutation matrix is uniquely determined for Bruhat while it is not for PLU.

[tscrim]

comment:30

w0 A = L P U = w0 U’ w0 P U and so A = U’ (w0 P) U with U, U’ being upper triangular matrices. Perhaps because it is not PLU it matters, which is different than the usual LU decomposition algorithm. I was confusing this with the B^-wB Bruhat decomposition.

[xcaruso]

comment:31

Yes, echelon_form in sage returns a PLU decomposition and not a LPU one.