Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

r""" 

Helper Functions For Freeness Of Hyperplane Arrangements 

 

This contains the algorithms to check for freeness of a hyperplane 

arrangement. See 

:meth:`sage.geometry.hyperplane_arrangement.HyperplaneArrangementElement.is_free` 

for details. 

 

.. NOTE:: 

 

This could be extended to a freeness check for more general modules 

over a polynomial ring. 

""" 

 

#***************************************************************************** 

# Copyright (C) 2015 Travis Scrimshaw <tscrimsh at umn.edu> 

# 

# This program is free software: you can redistribute it and/or modify 

# it under the terms of the GNU General Public License as published by 

# the Free Software Foundation, either version 2 of the License, or 

# (at your option) any later version. 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

 

from sage.matrix.constructor import matrix 

import sage.libs.singular.function_factory as fun_fact 

 

def less_generators(X): 

""" 

Reduce the generator matrix of the module defined by ``X``. 

 

This is Algorithm 6.4 in [BC2012]_ and relies on the row syzygies of 

the matrix ``X``. 

 

EXAMPLES:: 

 

sage: from sage.geometry.hyperplane_arrangement.check_freeness import less_generators 

sage: R.<x,y,z> = QQ[] 

sage: m = matrix([[1, 0, 0], [0, z, -1], [0, 0, 0], [0, y, 1]]) 

sage: less_generators(m) 

[ 1 0 0] 

[ 0 z -1] 

[ 0 y 1] 

""" 

R = X.base_ring() 

syz = fun_fact.ff.syz 

zero = R.zero() 

while True: 

Z = matrix(R, syz(X.transpose())) 

# get_column_independent_unit_positions 

J = range(Z.ncols()) 

K = [] 

for r in Z.rows(): 

for j in J: 

elt = r[j] 

if elt.is_unit(): 

K.append(j) 

J = [l for l in J if r[l] == zero] 

break 

if not K: # K is empty 

return X 

Kd = set(range(X.nrows())).difference(K) 

X = X.matrix_from_rows(sorted(Kd)) 

 

def construct_free_chain(A): 

""" 

Construct the free chain for the hyperplanes ``A``. 

 

ALGORITHM: 

 

We follow Algorithm 6.5 in [BC2012]_. 

 

INPUT: 

 

- ``A`` -- a hyperplane arrangement 

 

EXAMPLES:: 

 

sage: from sage.geometry.hyperplane_arrangement.check_freeness import construct_free_chain 

sage: H.<x,y,z> = HyperplaneArrangements(QQ) 

sage: A = H(z, y+z, x+y+z) 

sage: construct_free_chain(A) 

[ 

[1 0 0] [ 1 0 0] [ 0 1 0] 

[0 1 0] [ 0 z -1] [y + z 0 -1] 

[0 0 z], [ 0 y 1], [ x 0 1] 

] 

""" 

AL = list(A) 

if not AL: # Empty arrangement 

return [] 

 

S = A.parent().ambient_space().symmetric_space() 

# Compute the morphisms \phi_{H_j} : S^{1xR} \to S / <b_j> 

B = [H.to_symmetric_space() for H in AL] 

phi = [matrix(S, [[beta.derivative(x)] for x in S.gens()]) for beta in B] 

 

# Setup variables 

syz = fun_fact.ff.syz 

G = S.gens() 

r = len(G) 

indices = list(range(len(B))) 

X = [] 

 

# Helper function 

def next_step(indices, prev, T): 

for pos,i in enumerate(indices): 

U = prev * T 

mu = U * phi[i] 

mu = mu.stack(matrix.diagonal([B[i]]).dense_matrix()) 

row_syzygy = matrix(S, syz(mu.transpose())).matrix_from_columns(range(r)) 

Y = less_generators(row_syzygy) 

if not Y.is_square(): 

continue 

 

if len(indices) == 1: 

return [prev, Y] 

 

I = list(indices) 

I.pop(pos) 

ret = next_step(I, Y, U) 

if ret is not None: 

return [prev] + ret 

return None 

 

T = matrix.identity(S, r) 

for i in indices: 

mu = phi[i].stack(matrix.diagonal([B[i]]).dense_matrix()) 

row_syzygy = matrix(S, syz(mu.transpose())).matrix_from_columns(range(r)) 

Y = less_generators(row_syzygy) 

if not Y.is_square(): 

continue 

 

if len(indices) == 1: 

return [Y] 

 

I = list(indices) 

I.pop(i) 

ret = next_step(I, Y, T) 

if ret is not None: 

return ret 

return None