use std::fmt;
use std::sync::Arc;
use crate::field::{Fp, PrimeField};
use crate::homspace::HomSpace;
use crate::linalg::{DenseMat, SparseMat, SparseRow};
use crate::module::Module;
use crate::profile::{Site, hit};
use crate::quiver::ArrowId;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum HomError {
DifferentAlgebras,
MapCountMismatch { expected: usize, got: usize },
MapShapeMismatch {
vertex: u32,
expected: (usize, usize),
got: (usize, usize),
},
NonCanonicalEntry { vertex: u32, row: usize, col: usize },
SquareViolated { arrow: ArrowId },
EndpointMismatch,
}
impl fmt::Display for HomError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::DifferentAlgebras => f.write_str("modules live over different algebras"),
Self::MapCountMismatch { expected, got } => {
write!(f, "morphism has {got} maps, quiver has {expected} vertices")
}
Self::MapShapeMismatch {
vertex,
expected,
got,
} => write!(
f,
"map at vertex {vertex} is {}x{}, expected {}x{}",
got.0, got.1, expected.0, expected.1
),
Self::NonCanonicalEntry { vertex, row, col } => write!(
f,
"map at vertex {vertex} has a non-canonical entry at ({row}, {col}) for the modules' field"
),
Self::SquareViolated { arrow } => {
write!(f, "commuting square fails at arrow {}", arrow.0)
}
Self::EndpointMismatch => {
f.write_str("target of the first morphism is not the source of the second")
}
}
}
}
impl std::error::Error for HomError {}
#[derive(Clone, Debug)]
pub struct Morphism {
source: Module,
target: Module,
maps: Vec<DenseMat>,
}
impl PartialEq for Morphism {
fn eq(&self, other: &Morphism) -> bool {
self.source.ptr_eq(&other.source)
&& self.target.ptr_eq(&other.target)
&& self.maps == other.maps
}
}
impl Eq for Morphism {}
fn check_parallel(m: &Module, n: &Module) -> Result<(), HomError> {
if !Arc::ptr_eq(m.algebra(), n.algebra()) {
return Err(HomError::DifferentAlgebras);
}
Ok(())
}
impl Morphism {
pub fn new(
source: &Module,
target: &Module,
maps: Vec<DenseMat>,
) -> Result<Morphism, HomError> {
hit(Site::MorphismNew);
let (m, n) = (source, target);
check_parallel(m, n)?;
let quiver = m.algebra().quiver();
let num_vertices = quiver.num_vertices() as usize;
if maps.len() != num_vertices {
return Err(HomError::MapCountMismatch {
expected: num_vertices,
got: maps.len(),
});
}
for (v, map) in maps.iter().enumerate() {
let expected = (m.dim_at(v as u32), n.dim_at(v as u32));
let got = (map.rows(), map.cols());
if got != expected {
return Err(HomError::MapShapeMismatch {
vertex: v as u32,
expected,
got,
});
}
}
let field = m.field();
for (v, map) in maps.iter().enumerate() {
if let Some((row, col)) = map.first_noncanonical(&field) {
return Err(HomError::NonCanonicalEntry {
vertex: v as u32,
row,
col,
});
}
}
for i in 0..quiver.num_arrows() {
hit(Site::MorphismSquare);
let arrow = ArrowId(i as u32);
let (u, v) = (quiver.source(arrow), quiver.target(arrow));
let left = maps[u as usize].mul(n.map(arrow), &field);
let right = m.map(arrow).mul(&maps[v as usize], &field);
if left != right {
return Err(HomError::SquareViolated { arrow });
}
}
Ok(Morphism {
source: source.clone(),
target: target.clone(),
maps,
})
}
pub(crate) fn new_unchecked(source: &Module, target: &Module, maps: Vec<DenseMat>) -> Morphism {
debug_assert!(
Morphism::new(source, target, maps.clone()).is_ok(),
"new_unchecked: the maps are not an A-linear map of these modules"
);
Morphism {
source: source.clone(),
target: target.clone(),
maps,
}
}
#[inline]
pub fn source(&self) -> &Module {
&self.source
}
#[inline]
pub fn target(&self) -> &Module {
&self.target
}
#[inline]
pub fn map_at(&self, v: u32) -> &DenseMat {
&self.maps[v as usize]
}
pub fn then(&self, g: &Morphism) -> Result<Morphism, HomError> {
hit(Site::MorphismThen);
if !self.target.ptr_eq(&g.source) {
return Err(HomError::EndpointMismatch);
}
let field = self.source.field();
let maps = self
.maps
.iter()
.zip(&g.maps)
.map(|(a, b)| a.mul(b, &field))
.collect();
Ok(Morphism {
source: self.source.clone(),
target: g.target.clone(),
maps,
})
}
pub fn is_isomorphism(&self) -> bool {
let field = self.source.field();
self.maps
.iter()
.all(|m| m.rows() == m.cols() && m.rank(&field) == m.rows())
}
pub fn apply(&self, element: &[Vec<Fp>]) -> Vec<Vec<Fp>> {
assert_eq!(
element.len(),
self.maps.len(),
"apply: needs one vector per vertex"
);
let field = self.source.field();
self.maps
.iter()
.zip(element)
.map(|(map, x)| map.transpose().mul_vec(x, &field))
.collect()
}
pub fn is_zero(&self) -> bool {
self.maps
.iter()
.all(|m| (0..m.rows()).all(|r| m.row(r).iter().all(|v| v.is_zero())))
}
}
pub fn identity(m: &Module) -> Morphism {
let maps = m
.dim_vector()
.iter()
.map(|&d| DenseMat::identity(d))
.collect();
Morphism {
source: m.clone(),
target: m.clone(),
maps,
}
}
pub fn zero_morphism(m: &Module, n: &Module) -> Result<Morphism, HomError> {
check_parallel(m, n)?;
let maps = m
.dim_vector()
.iter()
.zip(n.dim_vector())
.map(|(&a, &b)| DenseMat::zero(a, b))
.collect();
Ok(Morphism {
source: m.clone(),
target: n.clone(),
maps,
})
}
pub(crate) fn hom_rows(m: &Module, n: &Module) -> Result<DenseMat, HomError> {
hit(Site::Hom);
check_parallel(m, n)?;
let field = m.field();
let (constraints, _) = square_constraints(m, n);
let kernel = constraints.kernel_basis(&field);
let mut rows = DenseMat::zero(kernel.rows(), constraints.cols());
for r in 0..kernel.rows() {
for &(idx, val) in kernel.row(r).entries() {
rows.set(r, idx, val);
}
}
Ok(rows)
}
pub fn hom(m: &Module, n: &Module) -> Result<Vec<Morphism>, HomError> {
Ok(HomSpace::new(m, n)?.into_basis())
}
fn square_constraints(m: &Module, n: &Module) -> (SparseMat, Vec<usize>) {
let field = m.field();
let quiver = m.algebra().quiver();
let num_vertices = quiver.num_vertices() as usize;
let mut offsets = Vec::with_capacity(num_vertices);
let mut total = 0usize;
for v in 0..num_vertices {
offsets.push(total);
total += m.dim_vector()[v] * n.dim_vector()[v];
}
let mut rows = Vec::new();
for idx in 0..quiver.num_arrows() {
let arrow = ArrowId(idx as u32);
let (u, v) = (quiver.source(arrow) as usize, quiver.target(arrow) as usize);
let ma = m.map(arrow);
let na = n.map(arrow);
for i in 0..m.dim_vector()[u] {
for j in 0..n.dim_vector()[v] {
let mut entries = Vec::new();
for c in 0..n.dim_vector()[u] {
let val = na.get(c, j);
if !val.is_zero() {
entries.push((offsets[u] + i * n.dim_vector()[u] + c, val));
}
}
for r in 0..m.dim_vector()[v] {
let val = ma.get(i, r);
if !val.is_zero() {
entries.push((offsets[v] + r * n.dim_vector()[v] + j, field.neg(val)));
}
}
let row = SparseRow::from_entries(entries, &field);
if !row.is_zero() {
rows.push(row);
}
}
}
}
(SparseMat::from_rows(rows, total), offsets)
}
pub fn hom_dim(m: &Module, n: &Module) -> Result<usize, HomError> {
hit(Site::HomDim);
check_parallel(m, n)?;
let (constraints, _) = square_constraints(m, n);
Ok(constraints.cols() - constraints.rank(&m.field()))
}
pub(crate) fn express_in_row_basis(
basis: &DenseMat,
vectors: &DenseMat,
field: &PrimeField,
) -> DenseMat {
hit(Site::ExpressInRowBasis);
let bt = basis.transpose();
let mut out = DenseMat::zero(vectors.rows(), basis.rows());
for r in 0..vectors.rows() {
let x = bt
.solve(vectors.row(r), field)
.expect("vector lies in the row span of the basis");
for (c, &v) in x.iter().enumerate() {
out.set(r, c, v);
}
}
out
}
fn solve_columns(a: &DenseMat, rhs: &DenseMat, field: &PrimeField) -> DenseMat {
hit(Site::SolveColumns);
let rt = rhs.transpose();
let mut out = DenseMat::zero(a.cols(), rhs.cols());
for j in 0..rhs.cols() {
let x = a
.solve(rt.row(j), field)
.expect("column lies in the column space");
for (i, &v) in x.iter().enumerate() {
out.set(i, j, v);
}
}
out
}
pub(crate) fn submodule_with_inclusion(
parent: &Module,
bases: Vec<DenseMat>,
) -> (Module, Morphism) {
hit(Site::Submodule);
let field = parent.field();
let quiver = parent.algebra().quiver();
debug_assert!(
bases.iter().all(|b| b.rank(&field) == b.rows()),
"submodule_with_inclusion: the spanning rows are not linearly independent"
);
let dims: Vec<usize> = bases.iter().map(DenseMat::rows).collect();
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (u, v) = (quiver.source(a) as usize, quiver.target(a) as usize);
let image = bases[u].mul(parent.map(a), &field);
express_in_row_basis(&bases[v], &image, &field)
})
.collect();
let sub = Module::new(parent.algebra().clone(), dims, maps)
.expect("a submodule of a module is a module");
let inclusion = Morphism::new_unchecked(&sub, parent, bases);
(sub, inclusion)
}
pub(crate) fn quotient_with_projection(parent: &Module, bases: &[DenseMat]) -> (Module, Morphism) {
hit(Site::Quotient);
let field = parent.field();
let quiver = parent.algebra().quiver();
let projections: Vec<DenseMat> = bases
.iter()
.map(|b| b.kernel_basis(&field).transpose())
.collect();
debug_assert!(
projections.iter().all(|q| q.rank(&field) == q.cols()),
"quotient_with_projection: the projection columns are not linearly independent"
);
let dims: Vec<usize> = projections.iter().map(DenseMat::cols).collect();
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (u, v) = (quiver.source(a) as usize, quiver.target(a) as usize);
let rhs = parent.map(a).mul(&projections[v], &field);
solve_columns(&projections[u], &rhs, &field)
})
.collect();
let quotient = Module::new(parent.algebra().clone(), dims, maps)
.expect("a quotient of a module is a module");
let projection = Morphism::new_unchecked(parent, "ient, projections);
(quotient, projection)
}
fn row_space_bases(f: &Morphism, field: &PrimeField, num_vertices: u32) -> Vec<DenseMat> {
(0..num_vertices)
.map(|v| f.map_at(v).row_space_basis(field))
.collect()
}
pub fn kernel(f: &Morphism) -> (Module, Morphism) {
hit(Site::HomKernel);
let m = f.source();
let field = m.field();
let bases: Vec<DenseMat> = (0..m.algebra().quiver().num_vertices())
.map(|v| f.map_at(v).transpose().kernel_basis(&field))
.collect();
submodule_with_inclusion(m, bases)
}
pub fn image(f: &Morphism) -> (Module, Morphism) {
hit(Site::HomImage);
let n = f.target();
let field = n.field();
let bases = row_space_bases(f, &field, n.algebra().quiver().num_vertices());
submodule_with_inclusion(n, bases)
}
pub fn cokernel(f: &Morphism) -> (Module, Morphism) {
hit(Site::HomCokernel);
let n = f.target();
let field = n.field();
let bases = row_space_bases(f, &field, n.algebra().quiver().num_vertices());
quotient_with_projection(n, &bases)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{an_with_relations, dual_numbers, linear_an};
use crate::module::direct_sum;
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
#[test]
fn hom_from_projective_has_the_dimension_of_the_module_at_the_vertex() {
let field = f5();
for algebra in [
linear_an(3, field),
an_with_relations(3, &[(0, 2)], field).unwrap(),
dual_numbers(field),
] {
let n = algebra.quiver().num_vertices();
let mut modules: Vec<Module> = Vec::new();
for v in 0..n {
modules.push(Module::simple(&algebra, v));
modules.push(Module::projective(&algebra, v));
modules.push(Module::injective(&algebra, v));
}
let parts: Vec<&Module> = modules.iter().take(3).collect();
let (sum, _, _) = direct_sum(&parts);
modules.push(sum);
for v in 0..n {
let pv = Module::projective(&algebra, v);
for m in &modules {
assert_eq!(
hom(&pv, m).unwrap().len(),
m.dim_at(v),
"hom(P_{v}, M) with dim M = {:?}",
m.dim_vector()
);
}
}
}
}
#[test]
fn hom_between_simples_is_delta() {
let field = f5();
let algebra = linear_an(3, field);
for i in 0..3 {
for j in 0..3 {
let si = Module::simple(&algebra, i);
let sj = Module::simple(&algebra, j);
assert_eq!(
hom_dim(&si, &sj).unwrap(),
usize::from(i == j),
"hom(S_{i}, S_{j})"
);
}
}
}
#[test]
fn endomorphisms_of_p0_plus_p1_over_a2_have_dimension_3() {
let field = f5();
let algebra = linear_an(2, field);
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
assert_eq!(hom_dim(&p0, &p1).unwrap(), 0);
assert_eq!(hom_dim(&p1, &p0).unwrap(), 1);
let (sum, _, _) = direct_sum(&[&p0, &p1]);
assert_eq!(hom_dim(&sum, &sum).unwrap(), 3);
}
#[test]
fn hom_rejects_modules_over_different_algebras() {
let field = f5();
let a = linear_an(3, field);
let b = linear_an(3, field);
let m = Module::simple(&a, 0);
let n = Module::simple(&b, 0);
assert_eq!(hom(&m, &n).unwrap_err(), HomError::DifferentAlgebras);
}
#[test]
fn hom_rejects_modules_over_different_fields() {
let a = linear_an(3, f5());
let b = linear_an(3, PrimeField::new(7).unwrap());
let m = Module::simple(&a, 0);
let n = Module::simple(&b, 0);
assert_eq!(hom(&m, &n).unwrap_err(), HomError::DifferentAlgebras);
}
#[test]
fn then_rejects_mismatched_endpoints() {
let field = f5();
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let s0 = Module::simple(&algebra, 0);
let f = hom(&p0, &s0).unwrap().remove(0);
let s0_copy = Module::simple(&algebra, 0);
assert_eq!(
f.then(&identity(&s0_copy)).unwrap_err(),
HomError::EndpointMismatch
);
assert!(f.then(&identity(&s0)).is_ok());
}
#[test]
fn morphism_equality_requires_pointer_identical_endpoints() {
let field = f5();
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p0_copy = Module::projective(&algebra, 0);
assert!(!p0.ptr_eq(&p0_copy));
assert!(p0.ptr_eq(&p0.clone()));
assert_ne!(identity(&p0), identity(&p0_copy));
assert_eq!(identity(&p0), identity(&p0.clone()));
}
#[test]
fn morphism_new_rejects_a_non_canonical_entry() {
let algebra = linear_an(2, PrimeField::new(2).unwrap());
let p0 = Module::projective(&algebra, 0);
let bad = DenseMat::from_rows(&[vec![f5().elem(3)]]);
let maps = vec![bad, DenseMat::identity(1)];
assert_eq!(
Morphism::new(&p0, &p0, maps).unwrap_err(),
HomError::NonCanonicalEntry {
vertex: 0,
row: 0,
col: 0,
}
);
}
#[test]
fn morphism_new_rejects_a_noncommuting_square() {
let field = f5();
let algebra = linear_an(2, field);
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let maps = vec![DenseMat::zero(1, 0), DenseMat::identity(1)];
assert_eq!(
Morphism::new(&p0, &p1, maps).unwrap_err(),
HomError::SquareViolated { arrow: ArrowId(0) }
);
}
#[test]
fn identity_is_neutral_for_composition() {
let field = f5();
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let s0 = Module::simple(&algebra, 0);
let f = hom(&p0, &s0).unwrap().remove(0);
assert_eq!(identity(&p0).then(&f).unwrap(), f);
assert_eq!(f.then(&identity(&s0)).unwrap(), f);
assert!(zero_morphism(&p0, &s0).unwrap().is_zero());
assert!(!f.is_zero());
}
#[test]
fn the_nonzero_map_p0_to_i2_over_a3_is_an_isomorphism() {
let field = f5();
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let i2 = Module::injective(&algebra, 2);
let basis = hom(&p0, &i2).unwrap();
assert_eq!(basis.len(), 1);
assert!(basis[0].is_isomorphism());
assert!(!zero_morphism(&p0, &p0).unwrap().is_isomorphism());
assert!(identity(&p0).is_isomorphism());
}
#[test]
fn apply_maps_row_vectors_through_the_vertex_matrices() {
let field = f5();
let algebra = linear_an(2, field);
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let f = hom(&p1, &p0).unwrap().remove(0);
let element = vec![vec![], vec![field.elem(2)]];
let image = f.apply(&element);
assert_eq!(image[0], vec![field.zero()]);
let expected = field.mul(field.elem(2), f.map_at(1).get(0, 0));
assert_eq!(image[1], vec![expected]);
}
#[test]
fn kernel_image_cokernel_satisfy_rank_nullity_and_compose_correctly() {
let field = f5();
let cases: Vec<(Module, Module)> = {
let a3 = linear_an(3, field);
let dn = dual_numbers(field);
let p0 = Module::projective(&a3, 0);
let p1 = Module::projective(&a3, 1);
let s0 = Module::simple(&a3, 0);
let i2 = Module::injective(&a3, 2);
let (sum, _, _) = direct_sum(&[&p0, &p1]);
let dp = Module::projective(&dn, 0);
vec![
(p0.clone(), s0),
(p0.clone(), i2),
(sum, p0),
(dp.clone(), dp),
]
};
for (m, n) in &cases {
for f in hom(m, n).unwrap() {
let (ker, ker_incl) = kernel(&f);
let (im, im_incl) = image(&f);
let (coker, coker_proj) = cokernel(&f);
for v in 0..m.algebra().quiver().num_vertices() {
assert_eq!(ker.dim_at(v) + im.dim_at(v), m.dim_at(v), "vertex {v}");
assert_eq!(im.dim_at(v) + coker.dim_at(v), n.dim_at(v), "vertex {v}");
}
assert_eq!(ker_incl.then(&f).unwrap(), zero_morphism(&ker, n).unwrap());
assert_eq!(
f.then(&coker_proj).unwrap(),
zero_morphism(m, &coker).unwrap()
);
let corestriction_maps = (0..m.algebra().quiver().num_vertices())
.map(|v| express_in_row_basis(im_incl.map_at(v), f.map_at(v), &field))
.collect();
let corestriction = Morphism::new(m, &im, corestriction_maps).unwrap();
assert_eq!(corestriction.then(&im_incl).unwrap(), f);
}
}
}
}