use std::fmt;
use std::sync::OnceLock;
use crate::field::{Fp, PrimeField};
use crate::hom::{HomError, Morphism, hom_rows};
use crate::linalg::{DenseMat, RowReducer};
use crate::module::Module;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum HomSpaceError {
SourceMismatch,
TargetMismatch,
IncompatibleSubspaces,
NotContained,
OutsideSubspace,
}
impl fmt::Display for HomSpaceError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::SourceMismatch => f.write_str("the morphism's source is not the space's source"),
Self::TargetMismatch => f.write_str("the morphism's target is not the space's target"),
Self::IncompatibleSubspaces => {
f.write_str("the subspaces do not share both endpoint modules")
}
Self::NotContained => {
f.write_str("the inner subspace is not contained in the ambient subspace")
}
Self::OutsideSubspace => {
f.write_str("the morphism lies outside the ambient subspace of the quotient")
}
}
}
}
impl std::error::Error for HomSpaceError {}
pub(crate) fn flat_row(f: &Morphism) -> Vec<Fp> {
let mut row = Vec::new();
for v in 0..f.source().algebra().quiver().num_vertices() {
let map = f.map_at(v);
for r in 0..map.rows() {
row.extend_from_slice(map.row(r));
}
}
row
}
fn flat_width(m: &Module, n: &Module) -> usize {
m.dim_vector()
.iter()
.zip(n.dim_vector())
.map(|(&a, &b)| a * b)
.sum()
}
fn morphism_from_flat(source: &Module, target: &Module, row: &[Fp]) -> Morphism {
let num_vertices = source.algebra().quiver().num_vertices();
let mut maps = Vec::with_capacity(num_vertices as usize);
let mut offset = 0;
for v in 0..num_vertices {
let (dm, dn) = (source.dim_at(v), target.dim_at(v));
let mut block = DenseMat::zero(dm, dn);
for r in 0..dm {
for c in 0..dn {
block.set(r, c, row[offset + r * dn + c]);
}
}
offset += dm * dn;
maps.push(block);
}
Morphism::new_unchecked(source, target, maps)
}
pub(crate) fn row_times(row: &[Fp], m: &DenseMat, field: &PrimeField) -> Vec<Fp> {
let mut out = vec![Fp::ZERO; m.cols()];
for (k, &c) in row.iter().enumerate() {
if c.is_zero() {
continue;
}
for (j, out_j) in out.iter_mut().enumerate() {
*out_j = field.add(*out_j, field.mul(c, m.get(k, j)));
}
}
out
}
pub(crate) fn rref_coords(rref: &DenseMat, v: &[Fp], field: &PrimeField) -> Option<Vec<Fp>> {
if rref.cols() != v.len() {
return None;
}
let coords: Vec<Fp> = (0..rref.rows())
.map(|r| {
let pivot = rref
.row(r)
.iter()
.position(|e| !e.is_zero())
.expect("a reduced row echelon basis has no zero row");
v[pivot]
})
.collect();
(row_times(&coords, rref, field) == v).then_some(coords)
}
pub(crate) fn rref_coords_many(
rref: &DenseMat,
rows: &DenseMat,
field: &PrimeField,
) -> Option<DenseMat> {
if rref.cols() != rows.cols() {
return None;
}
if rows.rows() == 0 {
return Some(DenseMat::zero(0, rref.rows()));
}
let pivots: Vec<usize> = (0..rref.rows())
.map(|r| {
rref.row(r)
.iter()
.position(|e| !e.is_zero())
.expect("a reduced row echelon basis has no zero row")
})
.collect();
let mut coords = DenseMat::zero(rows.rows(), rref.rows());
for r in 0..rows.rows() {
for (c, &pivot) in pivots.iter().enumerate() {
coords.set(r, c, rows.get(r, pivot));
}
}
(coords.mul(rref, field) == *rows).then_some(coords)
}
pub(crate) fn scale_morphism(f: &Morphism, c: Fp) -> Morphism {
let field = f.source().field();
let maps = (0..f.source().algebra().quiver().num_vertices())
.map(|v| {
let block = f.map_at(v);
let mut out = DenseMat::zero(block.rows(), block.cols());
for r in 0..block.rows() {
for j in 0..block.cols() {
out.set(r, j, field.mul(c, block.get(r, j)));
}
}
out
})
.collect();
Morphism::new_unchecked(f.source(), f.target(), maps)
}
fn check_endpoints(source: &Module, target: &Module, f: &Morphism) -> Result<(), HomSpaceError> {
if !f.source().ptr_eq(source) {
return Err(HomSpaceError::SourceMismatch);
}
if !f.target().ptr_eq(target) {
return Err(HomSpaceError::TargetMismatch);
}
Ok(())
}
pub(crate) fn stack_rows(matrices: &[&DenseMat], cols: usize) -> DenseMat {
let rows: Vec<Vec<Fp>> = matrices
.iter()
.flat_map(|m| (0..m.rows()).map(|r| m.row(r).to_vec()))
.collect();
if rows.is_empty() {
DenseMat::zero(0, cols)
} else {
DenseMat::from_rows(&rows)
}
}
pub(crate) fn deterministic_complement(
ambient: &DenseMat,
inner: &DenseMat,
field: &PrimeField,
) -> DenseMat {
let empty = DenseMat::zero(0, ambient.cols());
let mut reducer = RowReducer::new(ambient.cols());
for r in 0..inner.rows() {
if !reducer.push(inner.row(r), field) {
return empty;
}
}
let mut kept: Vec<Vec<Fp>> = Vec::new();
for r in 0..ambient.rows() {
if reducer.push(ambient.row(r), field) {
kept.push(ambient.row(r).to_vec());
}
}
if kept.is_empty() {
empty
} else {
DenseMat::from_rows(&kept)
}
}
#[derive(Clone, Debug)]
pub struct HomSpace {
source: Module,
target: Module,
flat: DenseMat,
basis: OnceLock<Vec<Morphism>>,
}
impl HomSpace {
pub fn new(m: &Module, n: &Module) -> Result<HomSpace, HomError> {
Ok(HomSpace {
source: m.clone(),
target: n.clone(),
flat: hom_rows(m, n)?,
basis: OnceLock::new(),
})
}
#[inline]
pub fn dim(&self) -> usize {
self.flat.rows()
}
#[inline]
pub fn source(&self) -> &Module {
&self.source
}
#[inline]
pub fn target(&self) -> &Module {
&self.target
}
pub fn basis_morphism(&self, i: usize) -> Morphism {
morphism_from_flat(&self.source, &self.target, self.flat.row(i))
}
pub fn basis_iter(&self) -> impl Iterator<Item = Morphism> + '_ {
(0..self.dim()).map(|i| self.basis_morphism(i))
}
pub fn basis(&self) -> &[Morphism] {
self.basis.get_or_init(|| self.basis_iter().collect())
}
pub fn into_basis(self) -> Vec<Morphism> {
self.into_parts().1
}
pub(crate) fn into_parts(self) -> (DenseMat, Vec<Morphism>) {
let HomSpace {
source,
target,
flat,
basis,
} = self;
let basis = basis.into_inner().unwrap_or_else(|| {
(0..flat.rows())
.map(|i| morphism_from_flat(&source, &target, flat.row(i)))
.collect()
});
(flat, basis)
}
pub fn is_compatible(&self, other: &HomSpace) -> bool {
self.source.ptr_eq(&other.source) && self.target.ptr_eq(&other.target)
}
pub fn morphism(&self, coords: &[Fp]) -> Morphism {
assert_eq!(
coords.len(),
self.dim(),
"morphism: needs one coordinate per basis element"
);
let field = self.source.field();
let row = row_times(coords, &self.flat, &field);
morphism_from_flat(&self.source, &self.target, &row)
}
pub fn coords(&self, f: &Morphism) -> Result<Vec<Fp>, HomSpaceError> {
check_endpoints(&self.source, &self.target, f)?;
let field = self.source.field();
Ok(self
.flat
.transpose()
.solve(&flat_row(f), &field)
.expect("the hom basis spans every morphism between the endpoints"))
}
pub fn subspace(&self, spanning: &[Morphism]) -> Result<HomSubspace, HomSpaceError> {
HomSubspace::spanned_by(&self.source, &self.target, spanning)
}
pub fn full_subspace(&self) -> HomSubspace {
let field = self.source.field();
HomSubspace {
source: self.source.clone(),
target: self.target.clone(),
basis: self.flat.row_space_basis(&field),
}
}
}
#[derive(Clone, Debug)]
pub struct HomSubspace {
source: Module,
target: Module,
basis: DenseMat,
}
impl PartialEq for HomSubspace {
fn eq(&self, other: &HomSubspace) -> bool {
self.source.ptr_eq(&other.source)
&& self.target.ptr_eq(&other.target)
&& self.basis == other.basis
}
}
impl Eq for HomSubspace {}
impl HomSubspace {
pub(crate) fn spanned_by(
source: &Module,
target: &Module,
spanning: &[Morphism],
) -> Result<HomSubspace, HomSpaceError> {
for f in spanning {
check_endpoints(source, target, f)?;
}
let field = source.field();
let rows: Vec<Vec<Fp>> = spanning.iter().map(flat_row).collect();
let stacked = if rows.is_empty() {
DenseMat::zero(0, flat_width(source, target))
} else {
DenseMat::from_rows(&rows)
};
Ok(HomSubspace {
source: source.clone(),
target: target.clone(),
basis: stacked.row_space_basis(&field),
})
}
#[inline]
pub fn source(&self) -> &Module {
&self.source
}
#[inline]
pub fn target(&self) -> &Module {
&self.target
}
#[inline]
pub fn dim(&self) -> usize {
self.basis.rows()
}
#[inline]
pub fn rref_basis(&self) -> &DenseMat {
&self.basis
}
pub fn basis_morphism(&self, r: usize) -> Morphism {
morphism_from_flat(&self.source, &self.target, self.basis.row(r))
}
pub fn contains(&self, f: &Morphism) -> Result<bool, HomSpaceError> {
Ok(self.witness_contains(f)?.is_some())
}
pub fn witness_contains(&self, f: &Morphism) -> Result<Option<Vec<Fp>>, HomSpaceError> {
check_endpoints(&self.source, &self.target, f)?;
let field = self.source.field();
Ok(rref_coords(&self.basis, &flat_row(f), &field))
}
pub fn quotient_by(&self, sub: &HomSubspace) -> Result<HomQuotient, HomSpaceError> {
if !(self.source.ptr_eq(&sub.source) && self.target.ptr_eq(&sub.target)) {
return Err(HomSpaceError::IncompatibleSubspaces);
}
let field = self.source.field();
if rref_coords_many(&self.basis, &sub.basis, &field).is_none() {
return Err(HomSpaceError::NotContained);
}
let complement = deterministic_complement(&self.basis, &sub.basis, &field);
Ok(HomQuotient {
subspace: sub.clone(),
complement,
})
}
}
#[derive(Clone, Debug)]
pub struct HomQuotient {
subspace: HomSubspace,
complement: DenseMat,
}
impl HomQuotient {
#[inline]
pub fn source(&self) -> &Module {
&self.subspace.source
}
#[inline]
pub fn target(&self) -> &Module {
&self.subspace.target
}
#[inline]
pub fn dim(&self) -> usize {
self.complement.rows()
}
#[inline]
pub fn subspace(&self) -> &HomSubspace {
&self.subspace
}
#[inline]
pub fn complement_basis(&self) -> &DenseMat {
&self.complement
}
pub fn representative(&self, coords: &[Fp]) -> Morphism {
assert_eq!(
coords.len(),
self.dim(),
"representative: needs one coordinate per complement row"
);
let field = self.subspace.source.field();
let row = row_times(coords, &self.complement, &field);
morphism_from_flat(&self.subspace.source, &self.subspace.target, &row)
}
pub fn reduce(&self, f: &Morphism) -> Result<(Vec<Fp>, Morphism), HomSpaceError> {
check_endpoints(&self.subspace.source, &self.subspace.target, f)?;
let field = self.subspace.source.field();
let stacked = stack_rows(
&[&self.complement, &self.subspace.basis],
self.complement.cols(),
);
let Some(x) = stacked.transpose().solve(&flat_row(f), &field) else {
return Err(HomSpaceError::OutsideSubspace);
};
let coords = x[..self.complement.rows()].to_vec();
let member_row = row_times(&x[self.complement.rows()..], &self.subspace.basis, &field);
let member = morphism_from_flat(&self.subspace.source, &self.subspace.target, &member_row);
Ok((coords, member))
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{commutative_square, dual_numbers, linear_an};
use crate::decompose::add_morphisms;
use crate::field::PrimeField;
use crate::hom::zero_morphism;
use crate::module::direct_sum;
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
fn fixture_endpoints() -> Vec<(Module, Module)> {
let field = f5();
let mut endpoints = Vec::new();
for algebra in [
linear_an(3, field),
dual_numbers(field),
commutative_square(field),
] {
let last = algebra.quiver().num_vertices() - 1;
let p = Module::projective(&algebra, 0);
let s = Module::simple(&algebra, last);
let (sum, _, _) = direct_sum(&[&p, &s, &p]);
endpoints.push((sum.clone(), sum));
endpoints.push((p, direct_sum(&[&s, &s]).0));
}
endpoints
}
fn fixture_spaces() -> Vec<HomSpace> {
fixture_endpoints()
.iter()
.map(|(m, n)| HomSpace::new(m, n).unwrap())
.collect()
}
fn unit(dim: usize, k: usize, field: &PrimeField) -> Vec<Fp> {
let mut v = vec![field.zero(); dim];
v[k] = field.one();
v
}
#[test]
fn basis_round_trip_recovers_coordinates() {
for space in fixture_spaces() {
let field = space.source().field();
for k in 0..space.dim() {
let coords = unit(space.dim(), k, &field);
let f = space.morphism(&coords);
assert_eq!(f, space.basis()[k], "unit {k} rebuilds basis element {k}");
assert_eq!(space.coords(&f).unwrap(), coords);
}
let mixed: Vec<Fp> = (0..space.dim() as i64).map(|i| field.elem(i + 1)).collect();
assert_eq!(space.coords(&space.morphism(&mixed)).unwrap(), mixed);
}
}
#[test]
fn flat_rows_stack_the_vertex_matrices_row_major() {
let algebra = linear_an(3, f5());
let p0 = Module::projective(&algebra, 0);
let space = HomSpace::new(&p0, &p0).unwrap();
assert_eq!(space.flat.cols(), 3);
assert_eq!(space.dim(), 1);
let expected = flat_row(&space.basis()[0]);
assert_eq!(space.flat.row(0), expected.as_slice());
}
#[test]
fn recomputed_compatible_spaces_have_identical_bases() {
for (m, n) in fixture_endpoints() {
let first = HomSpace::new(&m, &n).unwrap();
let second = HomSpace::new(&m, &n).unwrap();
assert!(first.is_compatible(&second));
assert_eq!(first.flat.entries_u64(), second.flat.entries_u64());
for (f, g) in first.basis().iter().zip(second.basis()) {
assert_eq!(f, g);
}
}
}
#[test]
fn coords_rejects_wrong_endpoints_with_typed_errors() {
let algebra = linear_an(3, f5());
let p0 = Module::projective(&algebra, 0);
let s0 = Module::simple(&algebra, 0);
let space = HomSpace::new(&p0, &s0).unwrap();
let p0_copy = Module::projective(&algebra, 0);
let s0_copy = Module::simple(&algebra, 0);
let wrong_source = HomSpace::new(&p0_copy, &s0).unwrap().basis_morphism(0);
assert_eq!(
space.coords(&wrong_source).unwrap_err(),
HomSpaceError::SourceMismatch
);
let wrong_target = HomSpace::new(&p0, &s0_copy).unwrap().basis_morphism(0);
assert_eq!(
space.coords(&wrong_target).unwrap_err(),
HomSpaceError::TargetMismatch
);
assert_eq!(
space
.subspace(std::slice::from_ref(&wrong_target))
.unwrap_err(),
HomSpaceError::TargetMismatch
);
let full = space.full_subspace();
assert_eq!(
full.contains(&wrong_source).unwrap_err(),
HomSpaceError::SourceMismatch
);
let quotient = full.quotient_by(&space.subspace(&[]).unwrap()).unwrap();
assert_eq!(
quotient.reduce(&wrong_source).unwrap_err(),
HomSpaceError::SourceMismatch
);
}
#[test]
fn hom_space_new_rejects_modules_over_different_algebras() {
let a = linear_an(3, f5());
let b = linear_an(3, f5());
let m = Module::simple(&a, 0);
let n = Module::simple(&b, 0);
assert_eq!(
HomSpace::new(&m, &n).unwrap_err(),
HomError::DifferentAlgebras
);
}
#[test]
fn subspace_rref_is_invariant_under_permuted_and_rescaled_spanning_sets() {
for space in fixture_spaces() {
if space.dim() < 2 {
continue;
}
let field = space.source().field();
let f = space.morphism(&unit(space.dim(), 0, &field));
let g = space.morphism(&unit(space.dim(), 1, &field));
let mut mixed = unit(space.dim(), 0, &field);
mixed[1] = field.elem(2);
let h = space.morphism(&mixed);
let scaled_coords: Vec<Fp> = unit(space.dim(), 1, &field)
.iter()
.map(|&c| field.mul(c, field.elem(3)))
.collect();
let g_scaled = space.morphism(&scaled_coords);
let first = space.subspace(&[f.clone(), g.clone(), h.clone()]).unwrap();
let second = space.subspace(&[h, g_scaled, f]).unwrap();
assert_eq!(first, second);
assert_eq!(
first.rref_basis().entries_u64(),
second.rref_basis().entries_u64()
);
assert_eq!(first.dim(), 2);
}
}
#[test]
fn empty_spanning_set_gives_the_zero_subspace() {
for space in fixture_spaces() {
let sub = space.subspace(&[]).unwrap();
assert_eq!(sub.dim(), 0);
let zero = zero_morphism(space.source(), space.target()).unwrap();
assert_eq!(sub.witness_contains(&zero).unwrap(), Some(Vec::new()));
if space.dim() > 0 {
assert!(!sub.contains(&space.basis()[0]).unwrap());
}
}
}
#[test]
fn witness_contains_returns_solving_coordinates() {
for space in fixture_spaces() {
if space.dim() < 2 {
continue;
}
let field = space.source().field();
let sub = space
.subspace(&[space.basis()[0].clone(), space.basis()[1].clone()])
.unwrap();
let mut coords = unit(space.dim(), 0, &field);
coords[1] = field.elem(4);
let f = space.morphism(&coords);
let witness = sub.witness_contains(&f).unwrap().expect("f spans inside");
let rebuilt = morphism_from_flat(
space.source(),
space.target(),
&row_times(&witness, sub.rref_basis(), &field),
);
assert_eq!(rebuilt, f, "witness coordinates rebuild the morphism");
if space.dim() > 2 {
let outside = space.morphism(&unit(space.dim(), 2, &field));
assert_eq!(sub.witness_contains(&outside).unwrap(), None);
}
}
}
#[test]
fn complement_rule_is_deterministic_across_recomputation() {
for (m, n) in fixture_endpoints() {
let build = |space: &HomSpace| {
let z = space.full_subspace();
let sub = space.subspace(&space.basis()[..1]).unwrap();
z.quotient_by(&sub).unwrap()
};
let first_space = HomSpace::new(&m, &n).unwrap();
let second_space = HomSpace::new(&m, &n).unwrap();
if first_space.dim() == 0 {
continue;
}
let first = build(&first_space);
let second = build(&second_space);
assert_eq!(
first.complement_basis().entries_u64(),
second.complement_basis().entries_u64()
);
assert_eq!(
first.subspace().rref_basis().entries_u64(),
second.subspace().rref_basis().entries_u64()
);
}
}
#[test]
fn complement_rows_come_from_the_ambient_rref_in_scan_order() {
for space in fixture_spaces() {
let z = space.full_subspace();
let sub = space.subspace(&[]).unwrap();
let quotient = z.quotient_by(&sub).unwrap();
assert_eq!(
quotient.complement_basis().entries_u64(),
z.rref_basis().entries_u64(),
"the complement of the zero subspace keeps every ambient row"
);
}
}
#[test]
fn quotient_reduce_returns_complement_coordinates_plus_a_subspace_member() {
for space in fixture_spaces() {
let field = space.source().field();
let z = space.full_subspace();
for sub_size in 0..=space.dim().min(2) {
let sub = space.subspace(&space.basis()[..sub_size]).unwrap();
let quotient = z.quotient_by(&sub).unwrap();
assert_eq!(quotient.dim() + sub.dim(), z.dim());
let mut probes: Vec<Morphism> = space.basis().to_vec();
if space.dim() > 0 {
let mixed: Vec<Fp> =
(0..space.dim() as i64).map(|i| field.elem(i + 2)).collect();
probes.push(space.morphism(&mixed));
}
for f in &probes {
let (coords, member) = quotient.reduce(f).unwrap();
assert_eq!(coords.len(), quotient.dim());
assert!(sub.contains(&member).unwrap());
let rebuilt = add_morphisms("ient.representative(&coords), &member);
assert_eq!(rebuilt, *f, "representative + member = original");
}
}
}
}
#[test]
fn reduce_rejects_an_element_outside_the_ambient_subspace() {
for space in fixture_spaces() {
if space.dim() < 2 {
continue;
}
let z = space.subspace(&space.basis()[..1]).unwrap();
let sub = space.subspace(&[]).unwrap();
let quotient = z.quotient_by(&sub).unwrap();
assert_eq!(
quotient.reduce(&space.basis()[1]).unwrap_err(),
HomSpaceError::OutsideSubspace
);
}
}
#[test]
fn quotient_by_rejects_incompatible_and_uncontained_subspaces() {
let algebra = linear_an(3, f5());
let p0 = Module::projective(&algebra, 0);
let s0 = Module::simple(&algebra, 0);
let space = HomSpace::new(&p0, &s0).unwrap();
assert!(space.dim() >= 1);
let small = space.subspace(&[]).unwrap();
let full = space.full_subspace();
assert_eq!(
small.quotient_by(&full).unwrap_err(),
HomSpaceError::NotContained
);
let p0_copy = Module::projective(&algebra, 0);
let other_space = HomSpace::new(&p0_copy, &s0).unwrap();
assert_eq!(
full.quotient_by(&other_space.full_subspace()).unwrap_err(),
HomSpaceError::IncompatibleSubspaces
);
}
}