Skip to content

Conversation

mkoeppe
Copy link
Contributor

@mkoeppe mkoeppe commented Mar 29, 2024

We use morphisms of CombinatorialFreeModules (each of which has a distinguished finite or enumerated basis indexed by arbitrary objects) as matrices whose rows and columns are indexed by arbitrary objects (row_keys, column_keys).

Example:

        sage: M = matrix([[1,2,3], [4,5,6]],
        ....:            column_keys=['a','b','c'], row_keys=['u','v']); M
        Generic morphism:
          From: Free module generated by {'a', 'b', 'c'} over Integer Ring
          To:   Free module generated by {'u', 'v'} over Integer Ring

Example application done here on the PR: The incidence matrix of a graph or digraph. Returning it as a morphism instead of a matrix has the benefit of keeping the vertices and edges with the result. This new behavior is activated by special values for the existing parameters vertices and edges.

            sage: D12 = posets.DivisorLattice(12).hasse_diagram()
            sage: phi_VE = D12.incidence_matrix(vertices=True, edges=True); phi_VE
            Generic morphism:
              From: Free module generated by
                      {(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (4, 12), (6, 12)}
                    over Integer Ring
              To:   Free module generated by {1, 2, 3, 4, 6, 12} over Integer Ring
            sage: print(phi_VE._unicode_art_matrix())
                         (1, 2)  (1, 3)  (2, 4)  (2, 6)  (3, 6) (4, 12) (6, 12)
                      1⎛     -1      -1       0       0       0       0       0⎞
                      2⎜      1       0      -1      -1       0       0       0⎟
                      3⎜      0       1       0       0      -1       0       0⎟
                      4⎜      0       0       1       0       0      -1       0⎟
                      6⎜      0       0       0       1       1       0      -1⎟
                     12⎝      0       0       0       0       0       1       1⎠

📝 Checklist

  • The title is concise and informative.
  • The description explains in detail what this PR is about.
  • I have linked a relevant issue or discussion.
  • I have created tests covering the changes.
  • I have updated the documentation accordingly.

⌛ Dependencies

Matthias Koeppe and others added 25 commits March 29, 2024 13:59
…hods _repr_matrix, _ascii_art_matrix, _unicode_art_matrix
@gmou3
Copy link
Contributor

gmou3 commented Mar 31, 2024

It looks ok. I am thinking however that it may complicate the code. E.g., in linear_matroid.pyx, do we gain something by having the morphism option internally coded?

Another small comment: in action.pyx there appear to be a few docstring formatting inconsistencies. Lines (30, 92), 141-144, 199.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Mar 31, 2024

in action.pyx there appear to be a few docstring formatting inconsistencies. Lines (30, 92), 141-144, 199.

Thanks; these formatting changes are coming from the dependency #37607. I agree that some further improvements are possible to make the formatting more consistent, but I don't want to do it on this PR.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Mar 31, 2024

I am thinking however that it may complicate the code. E.g., in linear_matroid.pyx, do we gain something by having the morphism option internally coded?

I don't think the code got more complicated. (The description of the options did get more complicated.) What is gained is the improved connection to the central structure using which algebraic combinatorics is expressed in Sage, the CombinatorialFreeModule.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Mar 31, 2024

@gmou3 By the way, what's still missing is the implementation of the roundtrip:

sage: M = matroids.catalog.Fano()
sage: A = M.representation(order=True)
Generic morphism:
  From: Free module generated by {'a', 'b', 'c', 'd', 'e', 'f', 'g'} over Finite Field of size 2
  To:   Free module generated by {0, 1, 2} over Finite Field of size 2
sage: Matroid(A)  # error

@gmou3
Copy link
Contributor

gmou3 commented Mar 31, 2024

I am thinking however that it may complicate the code. E.g., in linear_matroid.pyx, do we gain something by having the morphism option internally coded?

I don't think the code got more complicated. (The description of the options did get more complicated.) What is gained is the improved connection to the central structure using which algebraic combinatorics is expressed in Sage, the CombinatorialFreeModule.

Ok. This is the more general comment I would raise, that things appear to be getting a bit baroque. Also in graph, matrix. But you can judge this better than me.

@gmou3 By the way, what's still missing is the implementation of the roundtrip:

sage: M = matroids.catalog.Fano()
sage: A = M.representation(order=True)
Generic morphism:
  From: Free module generated by {'a', 'b', 'c', 'd', 'e', 'f', 'g'} over Finite Field of size 2
  To:   Free module generated by {0, 1, 2} over Finite Field of size 2
sage: Matroid(A)  # error

I could fix that. Similarly, with A = M.representation(labels=true) we get an error.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Apr 1, 2024

Lint and Build&Test failures are unrelated.

Copy link
Contributor

@gmou3 gmou3 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fine by me. I'll play around with adding the matroid morphism input after this is merged.

Copy link
Contributor

@gmou3 gmou3 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As per the Developer Guide.

Copy link

github-actions bot commented Apr 9, 2024

Documentation preview for this PR (built with commit 3e71e20; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Apr 20, 2024

Merged the latest version of the dependency #37514.

Any remaining concerns, or may I set to "positive review"?

@gmou3
Copy link
Contributor

gmou3 commented Apr 20, 2024

None from me.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Apr 20, 2024

Thanks!

@vbraun
Copy link
Member

vbraun commented Apr 24, 2024

doesn't work, ci fails

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Apr 28, 2024

All tests pass. Failure of "test modularized distributions" is unrelated.

vbraun pushed a commit to vbraun/sage that referenced this pull request Apr 28, 2024
sagemathgh-37692: `matrix`, `Graph.incidence_matrix`, `LinearMatroid.representation`: Support constructing `Hom(CombinatorialFreeModule)` elements
    
<!-- ^ Please provide a concise and informative title. -->
<!-- ^ Don't put issue numbers in the title, do this in the PR
description below. -->
<!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method
to calculate 1 + 2". -->
<!-- v Describe your changes below in detail. -->
<!-- v Why is this change required? What problem does it solve? -->
<!-- v If this PR resolves an open issue, please link to it here. For
example, "Fixes sagemath#12345". -->

We use morphisms of `CombinatorialFreeModule`s (each of which has a
distinguished finite or enumerated basis indexed by arbitrary objects)
as matrices whose rows and columns are indexed by arbitrary objects
(`row_keys`, `column_keys`).

Example:
```
        sage: M = matrix([[1,2,3], [4,5,6]],
        ....:            column_keys=['a','b','c'], row_keys=['u','v']);
M
        Generic morphism:
          From: Free module generated by {'a', 'b', 'c'} over Integer
Ring
          To:   Free module generated by {'u', 'v'} over Integer Ring
```

Example application done here on the PR: The incidence matrix of a graph
or digraph. Returning it as a morphism instead of a matrix has the
benefit of keeping the vertices and edges with the result. This new
behavior is activated by special values for the existing parameters
`vertices` and `edges`.
```
            sage: D12 = posets.DivisorLattice(12).hasse_diagram()
            sage: phi_VE = D12.incidence_matrix(vertices=True,
edges=True); phi_VE
            Generic morphism:
              From: Free module generated by
                      {(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (4, 12),
(6, 12)}
                    over Integer Ring
              To:   Free module generated by {1, 2, 3, 4, 6, 12} over
Integer Ring
            sage: print(phi_VE._unicode_art_matrix())
                         (1, 2)  (1, 3)  (2, 4)  (2, 6)  (3, 6) (4, 12)
(6, 12)
                      1⎛     -1      -1       0       0       0       0
0⎞
                      2⎜      1       0      -1      -1       0       0
0⎟
                      3⎜      0       1       0       0      -1       0
0⎟
                      4⎜      0       0       1       0       0      -1
0⎟
                      6⎜      0       0       0       1       1       0
-1⎟
                     12⎝      0       0       0       0       0       1
1⎠
```



### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [ ] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation accordingly.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
- Depends on sagemath#37607
- Depends on sagemath#37514
- Depends on sagemath#37606
- Depends on sagemath#37646
    
URL: sagemath#37692
Reported by: Matthias Köppe
Reviewer(s): gmou3
@vbraun vbraun merged commit f0a2850 into sagemath:develop May 2, 2024
vbraun pushed a commit to vbraun/sage that referenced this pull request May 9, 2024
sagemathgh-37940: Support morphisms in `Matroid` constructor
    
This follows the merging of sagemath#37692 and it enables the (re-)feeding of a
linear matroid's morphism representation into the `Matroid` constructor.

Example:
```
sage: M = matroids.catalog.Fano()
sage: A = M.representation(order=True); A
Generic morphism:
  From: Free module generated by {'a', 'b', 'c', 'd', 'e', 'f', 'g'}
over Finite Field of size 2
  To:   Free module generated by {0, 1, 2} over Finite Field of size 2
sage: Matroid(A)
Binary matroid of rank 3 on 7 elements, type (3, 0)
```
    
URL: sagemath#37940
Reported by: gmou3
Reviewer(s): gmou3, Matthias Köppe, Travis Scrimshaw
vbraun pushed a commit to vbraun/sage that referenced this pull request May 11, 2024
sagemathgh-37940: Support morphisms in `Matroid` constructor
    
This follows the merging of sagemath#37692 and it enables the (re-)feeding of a
linear matroid's morphism representation into the `Matroid` constructor.

Example:
```
sage: M = matroids.catalog.Fano()
sage: A = M.representation(order=True); A
Generic morphism:
  From: Free module generated by {'a', 'b', 'c', 'd', 'e', 'f', 'g'}
over Finite Field of size 2
  To:   Free module generated by {0, 1, 2} over Finite Field of size 2
sage: Matroid(A)
Binary matroid of rank 3 on 7 elements, type (3, 0)
```
    
URL: sagemath#37940
Reported by: gmou3
Reviewer(s): gmou3, Matthias Köppe, Travis Scrimshaw
vbraun pushed a commit to vbraun/sage that referenced this pull request May 11, 2024
sagemathgh-37955: `Graph.{[weighted_]adjacency_matrix,kirchhoff_matrix}`: Support constructing `End(CombinatorialFreeModule)` elements
    
<!-- ^ Please provide a concise and informative title. -->
<!-- ^ Don't put issue numbers in the title, do this in the PR
description below. -->
<!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method
to calculate 1 + 2". -->
<!-- v Describe your changes below in detail. -->
<!-- v Why is this change required? What problem does it solve? -->
<!-- v If this PR resolves an open issue, please link to it here. For
example, "Fixes sagemath#12345". -->

This is a follow-up after
- sagemath#37692

... to cover a few more methods. The methods can now create
endomorphisms of free modules whose bases are indexed by the vertices.
To help with this, we make the `matrix` constructor a bit more flexible.

This is also preparation for making the spectral graph theory methods
ready for `CombinatorialFreeModule`:
- sagemath#37943

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#37955
Reported by: Matthias Köppe
Reviewer(s): David Coudert, Matthias Köppe
vbraun pushed a commit to vbraun/sage that referenced this pull request May 12, 2024
sagemathgh-37940: Support morphisms in `Matroid` constructor
    
This follows the merging of sagemath#37692 and it enables the (re-)feeding of a
linear matroid's morphism representation into the `Matroid` constructor.

Example:
```
sage: M = matroids.catalog.Fano()
sage: A = M.representation(order=True); A
Generic morphism:
  From: Free module generated by {'a', 'b', 'c', 'd', 'e', 'f', 'g'}
over Finite Field of size 2
  To:   Free module generated by {0, 1, 2} over Finite Field of size 2
sage: Matroid(A)
Binary matroid of rank 3 on 7 elements, type (3, 0)
```
    
URL: sagemath#37940
Reported by: gmou3
Reviewer(s): gmou3, Matthias Köppe, Travis Scrimshaw
vbraun pushed a commit to vbraun/sage that referenced this pull request May 12, 2024
sagemathgh-37955: `Graph.{[weighted_]adjacency_matrix,kirchhoff_matrix}`: Support constructing `End(CombinatorialFreeModule)` elements
    
<!-- ^ Please provide a concise and informative title. -->
<!-- ^ Don't put issue numbers in the title, do this in the PR
description below. -->
<!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method
to calculate 1 + 2". -->
<!-- v Describe your changes below in detail. -->
<!-- v Why is this change required? What problem does it solve? -->
<!-- v If this PR resolves an open issue, please link to it here. For
example, "Fixes sagemath#12345". -->

This is a follow-up after
- sagemath#37692

... to cover a few more methods. The methods can now create
endomorphisms of free modules whose bases are indexed by the vertices.
To help with this, we make the `matrix` constructor a bit more flexible.

This is also preparation for making the spectral graph theory methods
ready for `CombinatorialFreeModule`:
- sagemath#37943

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#37955
Reported by: Matthias Köppe
Reviewer(s): David Coudert, Matthias Köppe
vbraun pushed a commit to vbraun/sage that referenced this pull request May 12, 2024
sagemathgh-37940: Support morphisms in `Matroid` constructor
    
This follows the merging of sagemath#37692 and it enables the (re-)feeding of a
linear matroid's morphism representation into the `Matroid` constructor.

Example:
```
sage: M = matroids.catalog.Fano()
sage: A = M.representation(order=True); A
Generic morphism:
  From: Free module generated by {'a', 'b', 'c', 'd', 'e', 'f', 'g'}
over Finite Field of size 2
  To:   Free module generated by {0, 1, 2} over Finite Field of size 2
sage: Matroid(A)
Binary matroid of rank 3 on 7 elements, type (3, 0)
```
    
URL: sagemath#37940
Reported by: gmou3
Reviewer(s): gmou3, Matthias Köppe, Travis Scrimshaw
vbraun pushed a commit to vbraun/sage that referenced this pull request May 12, 2024
sagemathgh-37955: `Graph.{[weighted_]adjacency_matrix,kirchhoff_matrix}`: Support constructing `End(CombinatorialFreeModule)` elements
    
<!-- ^ Please provide a concise and informative title. -->
<!-- ^ Don't put issue numbers in the title, do this in the PR
description below. -->
<!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method
to calculate 1 + 2". -->
<!-- v Describe your changes below in detail. -->
<!-- v Why is this change required? What problem does it solve? -->
<!-- v If this PR resolves an open issue, please link to it here. For
example, "Fixes sagemath#12345". -->

This is a follow-up after
- sagemath#37692

... to cover a few more methods. The methods can now create
endomorphisms of free modules whose bases are indexed by the vertices.
To help with this, we make the `matrix` constructor a bit more flexible.

This is also preparation for making the spectral graph theory methods
ready for `CombinatorialFreeModule`:
- sagemath#37943

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#37955
Reported by: Matthias Köppe
Reviewer(s): David Coudert, Matthias Köppe
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants