use std::fmt;
use std::sync::Arc;
use crate::algebra::{Algebra, BasisIdx};
use crate::field::{Fp, PrimeField};
use crate::hom::Morphism;
use crate::linalg::DenseMat;
use crate::profile::{Site, hit};
use crate::quiver::{ArrowId, PathWord, QuiverError};
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ModuleError {
DimsLengthMismatch { expected: usize, got: usize },
MapCountMismatch { expected: usize, got: usize },
MapShapeMismatch {
arrow: ArrowId,
expected: (usize, usize),
got: (usize, usize),
},
NonCanonicalEntry {
arrow: ArrowId,
row: usize,
col: usize,
},
RelationActsNonzero { index: usize },
}
impl fmt::Display for ModuleError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::DimsLengthMismatch { expected, got } => {
write!(f, "dims has {got} entries, quiver has {expected} vertices")
}
Self::MapCountMismatch { expected, got } => {
write!(f, "maps has {got} matrices, quiver has {expected} arrows")
}
Self::MapShapeMismatch {
arrow,
expected,
got,
} => write!(
f,
"map for arrow {} is {}x{}, expected {}x{}",
arrow.0, got.0, got.1, expected.0, expected.1
),
Self::NonCanonicalEntry { arrow, row, col } => write!(
f,
"map for arrow {} has a non-canonical entry at ({row}, {col}) for the algebra's field",
arrow.0
),
Self::RelationActsNonzero { index } => {
write!(f, "relation {index} acts as a nonzero matrix")
}
}
}
}
impl std::error::Error for ModuleError {}
#[derive(Clone, Debug)]
pub struct Module(Arc<ModuleInner>);
#[derive(Debug)]
struct ModuleInner {
algebra: Arc<Algebra>,
dims: Vec<usize>,
maps: Vec<DenseMat>,
}
fn is_zero_mat(m: &DenseMat) -> bool {
(0..m.rows()).all(|r| m.row(r).iter().all(|v| v.is_zero()))
}
impl Module {
pub fn new(
algebra: Arc<Algebra>,
dims: Vec<usize>,
maps: Vec<DenseMat>,
) -> Result<Module, ModuleError> {
hit(Site::ModuleNew);
let field = algebra.field();
let quiver = algebra.quiver();
let num_vertices = quiver.num_vertices() as usize;
if dims.len() != num_vertices {
return Err(ModuleError::DimsLengthMismatch {
expected: num_vertices,
got: dims.len(),
});
}
if maps.len() != quiver.num_arrows() {
return Err(ModuleError::MapCountMismatch {
expected: quiver.num_arrows(),
got: maps.len(),
});
}
for (i, map) in maps.iter().enumerate() {
let arrow = ArrowId(i as u32);
let expected = (
dims[quiver.source(arrow) as usize],
dims[quiver.target(arrow) as usize],
);
let got = (map.rows(), map.cols());
if got != expected {
return Err(ModuleError::MapShapeMismatch {
arrow,
expected,
got,
});
}
}
for (i, map) in maps.iter().enumerate() {
if let Some((row, col)) = map.first_noncanonical(&field) {
return Err(ModuleError::NonCanonicalEntry {
arrow: ArrowId(i as u32),
row,
col,
});
}
}
for (index, relation) in algebra.relations().iter().enumerate() {
hit(Site::ModuleRelationCheck);
let source = relation.source() as usize;
let target = relation.target() as usize;
let mut acc = DenseMat::zero(dims[source], dims[target]);
for (coeff, word) in relation.terms() {
let mut action = DenseMat::identity(dims[source]);
for &a in word.arrows() {
action = action.mul(&maps[a.index()], &field);
}
for r in 0..acc.rows() {
for c in 0..acc.cols() {
let scaled = field.mul(*coeff, action.get(r, c));
acc.set(r, c, field.add(acc.get(r, c), scaled));
}
}
}
if !is_zero_mat(&acc) {
return Err(ModuleError::RelationActsNonzero { index });
}
}
Ok(Module(Arc::new(ModuleInner {
algebra,
dims,
maps,
})))
}
#[inline]
pub fn ptr_eq(&self, other: &Module) -> bool {
Arc::ptr_eq(&self.0, &other.0)
}
#[inline]
pub(crate) fn addr(&self) -> usize {
Arc::as_ptr(&self.0) as usize
}
pub fn zero(algebra: &Arc<Algebra>) -> Module {
let dims = vec![0; algebra.quiver().num_vertices() as usize];
let maps = vec![DenseMat::zero(0, 0); algebra.quiver().num_arrows()];
Module::new(algebra.clone(), dims, maps).expect("the zero module is a module")
}
pub fn simple(algebra: &Arc<Algebra>, v: u32) -> Module {
let quiver = algebra.quiver();
assert!(v < quiver.num_vertices(), "simple: vertex {v} out of range");
let dims: Vec<usize> = (0..quiver.num_vertices())
.map(|w| usize::from(w == v))
.collect();
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
DenseMat::zero(
dims[quiver.source(a) as usize],
dims[quiver.target(a) as usize],
)
})
.collect();
Module::new(algebra.clone(), dims, maps).expect("S_v is a module")
}
pub fn projective(algebra: &Arc<Algebra>, v: u32) -> Module {
hit(Site::ModuleProjective);
let quiver = algebra.quiver();
assert!(
v < quiver.num_vertices(),
"projective: vertex {v} out of range"
);
let mut pos = vec![usize::MAX; algebra.dim()];
let mut dims = vec![0usize; quiver.num_vertices() as usize];
for w in 0..quiver.num_vertices() {
let component = algebra.paths_between(v, w);
dims[w as usize] = component.len();
for (i, &b) in component.iter().enumerate() {
pos[b] = i;
}
}
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (s, t) = (quiver.source(a), quiver.target(a));
let mut mat = DenseMat::zero(dims[s as usize], dims[t as usize]);
for (row, &p) in algebra.paths_between(v, s).iter().enumerate() {
for &(q, c) in algebra.right_mul(p, a) {
mat.set(row, pos[q], c);
}
}
mat
})
.collect();
Module::new(algebra.clone(), dims, maps).expect("P_v is a module")
}
pub fn injective(algebra: &Arc<Algebra>, v: u32) -> Module {
hit(Site::ModuleInjective);
let quiver = algebra.quiver();
assert!(
v < quiver.num_vertices(),
"injective: vertex {v} out of range"
);
let mut pos = vec![usize::MAX; algebra.dim()];
let mut dims = vec![0usize; quiver.num_vertices() as usize];
for w in 0..quiver.num_vertices() {
let component = algebra.paths_between(w, v);
dims[w as usize] = component.len();
for (i, &b) in component.iter().enumerate() {
pos[b] = i;
}
}
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (s, t) = (quiver.source(a), quiver.target(a));
let mut mat = DenseMat::zero(dims[s as usize], dims[t as usize]);
for (col, &p) in algebra.paths_between(t, v).iter().enumerate() {
for &(q, c) in algebra.left_mul(a, p) {
mat.set(pos[q], col, c);
}
}
mat
})
.collect();
Module::new(algebra.clone(), dims, maps).expect("I_v is a module")
}
#[inline]
pub fn algebra(&self) -> &Arc<Algebra> {
&self.0.algebra
}
#[inline]
pub fn field(&self) -> PrimeField {
self.0.algebra.field()
}
#[inline]
pub fn dim_vector(&self) -> &[usize] {
&self.0.dims
}
#[inline]
pub fn dim_at(&self, v: u32) -> usize {
self.0.dims[v as usize]
}
pub fn total_dim(&self) -> usize {
self.0.dims.iter().sum()
}
pub fn is_zero(&self) -> bool {
self.0.dims.iter().all(|&d| d == 0)
}
#[inline]
pub fn map(&self, a: ArrowId) -> &DenseMat {
&self.0.maps[a.index()]
}
pub fn word_action(&self, word: &PathWord) -> Result<DenseMat, QuiverError> {
hit(Site::WordAction);
word.validate_in(self.0.algebra.quiver())?;
let field = self.field();
let mut acc = DenseMat::identity(self.0.dims[word.source() as usize]);
for &a in word.arrows() {
acc = acc.mul(&self.0.maps[a.index()], &field);
}
Ok(acc)
}
pub fn element_action(&self, terms: &[(BasisIdx, Fp)]) -> DenseMat {
hit(Site::ElementAction);
assert!(!terms.is_empty(), "element_action: terms are empty");
let basis = self.0.algebra.basis();
let source = basis[terms[0].0].source();
let target = basis[terms[0].0].target();
let field = self.field();
let mut acc = DenseMat::zero(self.0.dims[source as usize], self.0.dims[target as usize]);
for &(index, coeff) in terms {
let word = &basis[index];
assert!(
word.source() == source && word.target() == target,
"element_action: terms mix sources or targets"
);
let action = self
.word_action(word)
.expect("algebra basis words are valid in their own quiver");
for r in 0..acc.rows() {
for c in 0..acc.cols() {
let scaled = field.mul(coeff, action.get(r, c));
acc.set(r, c, field.add(acc.get(r, c), scaled));
}
}
}
acc
}
}
pub fn direct_sum(summands: &[&Module]) -> (Module, Vec<Morphism>, Vec<Morphism>) {
hit(Site::DirectSum);
assert!(!summands.is_empty(), "direct_sum: needs a summand");
let first = summands[0];
for s in &summands[1..] {
assert!(
Arc::ptr_eq(first.algebra(), s.algebra()),
"direct_sum: mixed algebras"
);
}
let quiver = first.algebra().quiver();
let n = quiver.num_vertices() as usize;
let field = first.field();
let mut offsets = vec![vec![0usize; n]; summands.len()];
let mut dims = vec![0usize; n];
for (k, s) in summands.iter().enumerate() {
for (v, dim) in dims.iter_mut().enumerate() {
offsets[k][v] = *dim;
*dim += s.dim_vector()[v];
}
}
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (u, w) = (quiver.source(a) as usize, quiver.target(a) as usize);
let mut mat = DenseMat::zero(dims[u], dims[w]);
for (k, s) in summands.iter().enumerate() {
let block = s.map(a);
for r in 0..block.rows() {
for c in 0..block.cols() {
mat.set(offsets[k][u] + r, offsets[k][w] + c, block.get(r, c));
}
}
}
mat
})
.collect();
let sum = Module::new(first.algebra().clone(), dims, maps)
.expect("a direct sum of modules is a module");
let mut inclusions = Vec::with_capacity(summands.len());
let mut projections = Vec::with_capacity(summands.len());
for (k, s) in summands.iter().enumerate() {
let mut incl = Vec::with_capacity(n);
let mut proj = Vec::with_capacity(n);
for (v, &offset) in offsets[k].iter().enumerate() {
let mut inc = DenseMat::zero(s.dim_vector()[v], sum.dim_vector()[v]);
let mut prj = DenseMat::zero(sum.dim_vector()[v], s.dim_vector()[v]);
for i in 0..s.dim_vector()[v] {
inc.set(i, offset + i, field.one());
prj.set(offset + i, i, field.one());
}
incl.push(inc);
proj.push(prj);
}
inclusions.push(Morphism::new_unchecked(s, &sum, incl));
projections.push(Morphism::new_unchecked(&sum, s, proj));
}
(sum, inclusions, projections)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{
an_with_relations, commutative_square, cyclic_nakayama, dual_numbers, linear_an,
};
use crate::hom::{identity, zero_morphism};
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
fn mat(field: &PrimeField, rows: &[&[i64]]) -> DenseMat {
let rows: Vec<Vec<Fp>> = rows
.iter()
.map(|r| r.iter().map(|&v| field.elem(v)).collect())
.collect();
DenseMat::from_rows(&rows)
}
#[test]
fn invertible_loop_action_is_rejected() {
let a = dual_numbers(f5());
let result = Module::new(a, vec![1], vec![mat(&f5(), &[&[1]])]);
assert_eq!(
result.unwrap_err(),
ModuleError::RelationActsNonzero { index: 0 }
);
}
#[test]
fn nilpotent_loop_action_is_accepted() {
let a = dual_numbers(f5());
let m = Module::new(a, vec![2], vec![mat(&f5(), &[&[0, 1], &[0, 0]])]).unwrap();
assert_eq!(m.total_dim(), 2);
assert!(!m.is_zero());
}
#[test]
fn commutative_square_relation_is_enforced() {
let a = commutative_square(f5());
let one = mat(&f5(), &[&[1]]);
let zero = mat(&f5(), &[&[0]]);
let rejected = Module::new(
a.clone(),
vec![1, 1, 1, 1],
vec![one.clone(), one.clone(), one.clone(), zero],
);
assert_eq!(
rejected.unwrap_err(),
ModuleError::RelationActsNonzero { index: 0 }
);
let accepted = Module::new(
a,
vec![1, 1, 1, 1],
vec![one.clone(), one.clone(), one.clone(), one],
);
assert!(accepted.is_ok());
}
#[test]
fn wrong_dims_length_is_rejected() {
let a = linear_an(3, f5());
let result = Module::new(a, vec![1, 1], vec![DenseMat::zero(1, 1); 2]);
assert_eq!(
result.unwrap_err(),
ModuleError::DimsLengthMismatch {
expected: 3,
got: 2
}
);
}
#[test]
fn wrong_map_shape_is_rejected() {
let a = linear_an(3, f5());
let maps = vec![DenseMat::zero(1, 1), DenseMat::zero(2, 1)];
let result = Module::new(a, vec![1, 1, 1], maps);
assert_eq!(
result.unwrap_err(),
ModuleError::MapShapeMismatch {
arrow: ArrowId(1),
expected: (1, 1),
got: (2, 1)
}
);
}
#[test]
fn zero_module_has_dimension_zero() {
let a = linear_an(3, f5());
let z = Module::zero(&a);
assert!(z.is_zero());
assert_eq!(z.total_dim(), 0);
assert_eq!(z.dim_vector(), &[0, 0, 0]);
}
#[test]
fn word_action_multiplies_arrow_matrices_in_word_order() {
let a = linear_an(3, f5());
let field = f5();
let p0 = Module::projective(&a, 0);
let word =
PathWord::from_arrows(a.quiver(), &[ArrowId(0), ArrowId(1)]).expect("path a·b in A_3");
let expected = p0.map(ArrowId(0)).mul(p0.map(ArrowId(1)), &field);
assert_eq!(p0.word_action(&word), Ok(expected));
let trivial = PathWord::trivial(a.quiver(), 0).unwrap();
assert_eq!(p0.word_action(&trivial), Ok(DenseMat::identity(1)));
}
#[test]
fn word_action_rejects_a_word_from_another_quiver() {
let a = linear_an(3, f5());
let other = dual_numbers(f5());
let p0 = Module::projective(&a, 0);
let word = PathWord::from_arrows(other.quiver(), &[ArrowId(0)]).unwrap();
assert_eq!(
p0.word_action(&word),
Err(QuiverError::EndpointsDisagree {
stored: (0, 0),
computed: (0, 1),
})
);
}
#[test]
fn element_action_sums_scaled_word_actions() {
let field = f5();
let a = commutative_square(field);
let p0 = Module::projective(&a, 0);
let ab = a
.path_index(&PathWord::from_arrows(a.quiver(), &[ArrowId(0), ArrowId(1)]).unwrap())
.unwrap()
.unwrap();
let action = p0.element_action(&[(ab, field.elem(3))]);
let word_mat = p0.word_action(&a.basis()[ab]).expect("basis word is valid");
for r in 0..action.rows() {
for c in 0..action.cols() {
assert_eq!(
action.get(r, c),
field.mul(field.elem(3), word_mat.get(r, c))
);
}
}
}
#[test]
#[should_panic(expected = "mix sources")]
fn element_action_rejects_mixed_endpoints() {
let a = linear_an(3, f5());
let p0 = Module::projective(&a, 0);
p0.element_action(&[(0, f5().one()), (1, f5().one())]);
}
#[test]
fn non_canonical_entry_is_rejected_before_relation_checks() {
let a = dual_numbers(PrimeField::new(2).unwrap());
let maps = vec![mat(&f5(), &[&[3]])];
assert_eq!(
Module::new(a, vec![1], maps).unwrap_err(),
ModuleError::NonCanonicalEntry {
arrow: ArrowId(0),
row: 0,
col: 0,
}
);
}
#[test]
fn simple_is_one_dimensional_at_its_vertex() {
let a = an_with_relations(3, &[(0, 2)], f5()).unwrap();
for v in 0..3 {
let s = Module::simple(&a, v);
let expected: Vec<usize> = (0..3).map(|w| usize::from(w == v as usize)).collect();
assert_eq!(s.dim_vector(), expected.as_slice());
}
}
#[test]
fn projective_dim_vectors_are_cartan_rows() {
for algebra in [
linear_an(3, f5()),
an_with_relations(3, &[(0, 2)], f5()).unwrap(),
cyclic_nakayama(&[2, 2, 2], f5()).unwrap(),
commutative_square(f5()),
] {
let cartan = algebra.cartan_matrix();
for v in 0..algebra.quiver().num_vertices() {
let p = Module::projective(&algebra, v);
assert_eq!(p.dim_vector(), cartan[v as usize].as_slice(), "P_{v}");
}
}
}
#[test]
fn injective_dim_vectors_are_cartan_columns() {
for algebra in [
linear_an(3, f5()),
an_with_relations(3, &[(0, 2)], f5()).unwrap(),
cyclic_nakayama(&[2, 2, 2], f5()).unwrap(),
commutative_square(f5()),
] {
let cartan = algebra.cartan_matrix();
for v in 0..algebra.quiver().num_vertices() {
let i = Module::injective(&algebra, v);
let column: Vec<usize> = cartan.iter().map(|row| row[v as usize]).collect();
assert_eq!(i.dim_vector(), column.as_slice(), "I_{v}");
}
}
}
#[test]
fn a3_mod_ab_projective_p0_has_dimension_vector_1_1_0() {
let a = an_with_relations(3, &[(0, 2)], f5()).unwrap();
let p0 = Module::projective(&a, 0);
assert_eq!(p0.dim_vector(), &[1, 1, 0]);
}
#[test]
fn direct_sum_projections_split_inclusions() {
let a = linear_an(3, f5());
let p0 = Module::projective(&a, 0);
let p1 = Module::projective(&a, 1);
let s2 = Module::simple(&a, 2);
let parts = [&p0, &p1, &s2];
let (sum, inclusions, projections) = direct_sum(&parts);
for v in 0..3 {
assert_eq!(
sum.dim_at(v),
parts.iter().map(|m| m.dim_at(v)).sum::<usize>()
);
}
for (k, part) in parts.iter().enumerate() {
assert_eq!(
inclusions[k].then(&projections[k]).unwrap(),
identity(part),
"π_{k} ∘ ι_{k}"
);
for (j, other) in parts.iter().enumerate() {
if j != k {
assert_eq!(
inclusions[j].then(&projections[k]).unwrap(),
zero_morphism(other, part).unwrap(),
"π_{k} ∘ ι_{j}"
);
}
}
}
}
}