## Attachment 'hyperplane.sage'

   1 r"""
2 AUTHOR:
3     -- David Perkinson (2013-6-21)
4
5 VERSION: -1
6
7 EXAMPLES: (see HArrangement, below)
8
9 #*****************************************************************************
10 #       Copyright (C) 2013 David Perkinson <[email protected]>
11 #
14 #*****************************************************************************
15 """
16
17 class AffSpace():
18     r"""
19     Class for an affine space (a translation of a linear subspace).
20
21     INPUT:
22
23     - W -- vector space
24     - p -- list representing a point in W
25
26     OUTPUT:
27
28     - AffSpace
29
30     EXAMPLES:
31
32         sage: a = AffSpace([1,0,0,0],VectorSpace(QQ,4))
33         sage: a.dim()
34         4
35         sage: a.point()
36         (1, 0, 0, 0)
37         sage: a.linear_part()
38         Vector space of dimension 4 over Rational Field
39         sage: a
40         Affine space p + W where:
41            p = [1, 0, 0, 0]
42            W = Vector space of dimension 4 over Rational Field.
43         sage: b = AffSpace((1,0,0,0),matrix(QQ,[[1,2,3,4]]).right_kernel())
44         sage: c = AffSpace((0,2,0,0),matrix(QQ,[[0,0,1,2]]).right_kernel())
45         sage: b.intersection(c)
46         Affine space p + W where:
47            p = (-3, 2, 0, 0)
48            W = Vector space of degree 4 and dimension 2 over Rational Field
49         Basis matrix:
50         [  1   0  -1 1/2]
51         [  0   1  -2   1].
52         sage: b < a
53         True
54         sage: c < b
55         False
56     """
57
58     def __init__(self, p, V):
59         self._linear_part = V
60         self._point = vector(V.base_field(),p)
61
62     def __repr__(self):
63         return "Affine space p + W where:\n   p = "+str(self._point)+"\n   W = "+str(self._linear_part)+"."
64
65     def __eq__(self, other):
66         V = self._linear_part
67         W = other._linear_part
68         if V==W and self._point-other._point in V:
69             return True
70         else:
71             return False
72
73     def __ne__(self, other):
74         return not self==other
75
76     def __le__(self, other):
77         V = self._linear_part
78         W = other._linear_part
79         if V.is_subspace(W) and self._point-other._point in W:
80             return True
81         else:
82             return False
83
84     def __lt__(self, other):
85         if self<=other and not self==other:
86             return True
87         else:
88             return False
89
90     def __ge__(self, other):
91         return other<=self
92
93     def __gt__(self, other):
94         return other<self
95
96     def __contains__(self,q):
97         return self._point - q in self._linear_part
98
99     def linear_part(self):
100         r"""
101         The linear part of the affine space.
102
103         INPUT:
104
105         - None
106
107         OUTPUT:
108
109         - vector space
110
111         EXAMPLES::
112
113             sage: A = AffSpace([2,3,1], matrix(QQ,[[1,2,3]]).right_kernel())
114             sage: A.linear_part()
115             Vector space of degree 3 and dimension 2 over Rational Field
116             Basis matrix:
117             [   1    0 -1/3]
118             [   0    1 -2/3]
119         """
120         return copy(self._linear_part)
121
122     def point(self):
123         r"""
124         A point p in the affine space.
125
126         INPUT:
127
128         - None
129
130         OUTPUT:
131
132         - vector
133
134         EXAMPLES::
135
136             sage: A = AffSpace([2,3,1], VectorSpace(QQ,3))
137             sage: A.point()
138             (2, 3, 1)
139         """
140         return copy(self._point)
141
142     def dim(self):
143         r"""
144         The dimension of the affine space.
145
146         INPUT:
147
148         - None
149
150         OUTPUT:
151
152         - Integer
153
154         EXAMPLES::
155
156             sage: a = AffSpace([1,0,0,0],VectorSpace(QQ,4))
157             sage: a.dim()
158             4
159         """
160         return self._linear_part.dimension()
161
162
163     def intersection(self,other):
164         r"""
165
166
167         INPUT:
168
169         -
170
171         OUTPUT:
172
173         -
174
175         EXAMPLES::
176
177
178         """
179         m = self._linear_part.matrix()
180         n = other._linear_part.matrix()
181         p = self._point
182         q = other._point
183         A = m.stack(n)
184         v = q-p
185         if A.rank()!=(A.stack(v)).rank():
186             return -1
187         else:
188             t = A.solve_left(v)
189             new_p = p + t[:m.nrows()]*m
190             new_V = self._linear_part.intersection(other._linear_part)
191             return AffSpace(new_p,new_V)
192
193     def isomorphism_with_Kn(self,v):
194         p = self._point
195         W = self._linear_part
196         V = VectorSpace(W.base(),W.dimension())
197         f = W.hom(V.gens())
198         return f(v-p)
199
200
201 class Hyperplane(AffSpace):
202     def __init__(self,H,K=QQ):
203         r"""
204         The argument H is a hyperplane, given as a list [a1,...an,a]
205         representing the equation a1x1 + ... + anxn = a. An optional field,
206         K, may also be provided.
207
208         INPUT:
209
210         - H -- list of integers representing a hyperplane
211         - K -- field (default = QQ)
212
213         OUTPUT:
214
215         - Hyperplane
216
217         EXAMPLES::
218
219             sage: h = Hyperplane([1,3,2,2,8])
220             sage: h
221             Hyperplane over Rational Field
222             (1, 3, 2, 2)*X = 8
223         """
224         m = matrix(K,H[:-1])
225         p = m.solve_right(vector([H[-1]]))
226         AffSpace.__init__(self,p,m.right_kernel())
227         self._raw_data = H
228         self._normal = vector(K,H[:-1])
229         self._field = K
230
231     def __repr__(self):
232         return "Hyperplane over "+str(self._field)+"\n"+str(self._normal)+"*X = "+str(self._raw_data[-1])
233
234     def equation(self,suppress_printing=False):
235         if not suppress_printing:
236             print str(self._field)+"\n"+str(self._normal)+"*X = "+str(self._raw_data[-1])
237         return deepcopy(self._raw_data)
238
239     def normal(self):
240         return self._normal
241
242     # orthogonalize target basis to get less distorted picture?
243     # random color option?
244     def show(self,r=None,**kwds):
245         if r==None:
246             r = 1
247         if self.dim()==1: # so the dimension of the ambient space is 2
248             p = self.point()
249             w = self.linear_part().matrix()
250             var('t')
251             parametric_plot(p+t*w[0],(t,-r,r)).show(**kwds)
252         elif self.dim()==2: # so the dimension of the ambient space is 3
253             p = self.point()
254             w = self.linear_part().matrix()
255             var('s t')
256             parametric_plot3d(p+s*w[0]+t*w[1],(s,-r,r),(t,-r,r)).show(**kwds)
257
258     def plot(self,r=None,**kwds):
259         if r==None:
260             r = 1
261         if self.dim()==1: # so the dimension of the ambient space is 2
262             p = self.point()
263             w = self.linear_part().matrix()
264             var('t')
265             return parametric_plot(p+t*w[0],(t,-r,r),**kwds)
266         elif self.dim()==2: # so the dimension of the ambient space is 3
267             p = self.point()
268             w = self.linear_part().matrix()
269             var('s t')
270             return parametric_plot3d(p+s*w[0]+t*w[1],(s,-r,r),(t,-r,r),**kwds)
271
272 class HArrangement():
273
274     def __init__(self,A,K=QQ,check_for_duplicates=True):
275         r"""
276         The argument A is a list of hyperplanes. Each hyperplane is given as a
277         list [a1,...an,a] representing the equation a1x1 + ... + anxn =
278         a. An optional field, K, may also be provided.  Multiple copies of a
279         hyperplane are not supported, and a check is performed by default to
280         remove duplicates.
281
282         INPUT:
283
284         - A -- list
285         - K -- field (default = QQ)
286         - check_for_duplicates -- boolean
287
288         OUTPUT:
289
290         - HArrangement
291
292         EXAMPLE::
293
294             sage: A = HArrangement(([1,0,0],[2,1,5]))
295             sage: A
296             Hyperplane arrangement of 2 hyperplanes over Rational Field of dimension 2, rank 2.
297             sage: C = B.essentialization()
298             sage: B.characteristic_polynomial()
299             x^4 - 6*x^3 + 11*x^2 - 6*x
300             sage: C.characteristic_polynomial()
301             x^3 - 6*x^2 + 11*x - 6
302             sage: G = graphs.CycleGraph(4)
303             sage: B = hyperplane_arrangements.graphical(G)
304             sage: B.is_essential()
305             False
306             sage: C = B.essentialization()
307             sage: B.characteristic_polynomial()
308             x^4 - 4*x^3 + 6*x^2 - 3*x
309             sage: G.chromatic_polynomial()
310             x^4 - 4*x^3 + 6*x^2 - 3*x
311             sage: C.characteristic_polynomial()
312             x^3 - 4*x^2 + 6*x - 3
313             sage: B.num_regions()
314             14
315             sage: C.num_regions()
316             14
317             sage: D = hyperplane_arrangements.semiorder(3)
318             sage: D.is_essential()
319             False
320             sage: D.num_regions()
321             19
322             sage: D.num_bounded_regions()
323             7
324         """
325         if hasattr(A,'Hrepresentation'):
326             self._from_polytope = True  # test to see if there is a polytope for the arrangement?
327             self._polytope = deepcopy(A)
328             self._hrepresentation = A.Hrepresentation()
329             self._raw_data = []
330             for h in A.Hrepresentation():
331                 hh = list(h)
332                 self._raw_data.append(hh[1:]+[-hh[0]])
333             A = self._raw_data
334         else:
335             self._from_polytope = False
336             self._raw_data = A
337         if check_for_duplicates:
338             self._hyperplanes = []
339             for h in A:
340                 H = Hyperplane(h,K)
341                 if any (H==k for k in self._hyperplanes)==False:
342                     self._hyperplanes.append(H)
343         else:
344             self._hyperplanes = [Hyperplane(H,K) for H in A]
345         self._base_field = K
346         self._dim = len(A[0])-1
347         self._ambient_space = VectorSpace(K,self._dim)
348
349     def __getattr__(self, name):
350
351         if not self.__dict__.has_key(name):
352             if name == '_characteristic_polynomial':
353                 self._set_characteristic_polynomial()
354                 return deepcopy(self.__dict__[name])
355             elif name == '_essentialization':
356                 self._set_essentialization()
357                 return self.__dict__[name]
358             elif name == '_intersection_poset':
359                 self._set_intersection_poset()
360                 return deepcopy(self.__dict__[name])
361             elif name == '_poincare_polynomial':
362                 self._set_poincare_polynomial()
363                 return deepcopy(self.__dict__[name])
364             elif name == '_rank':
365                 self._set_rank()
366                 return self.__dict__[name]
367             elif name == '_regions':
368                 self._set_regions()
369                 return self.__dict__[name]
370             else:
371                 raise AttributeError, name
372
373     def __repr__(self):
374         return "Hyperplane arrangement of "+str(len(self._hyperplanes))+ " hyperplanes over "+str(self._base_field)+" of dimension "+str(self._dim)+", rank "+str(self.rank())+"."
375
376     def hyperplanes(self):
377         r"""
378         Returns the hyperplanes of the arrangement.
379
380         INPUT:
381
382         - None
383
384         OUTPUT:
385
386         - list of Hyperplanes
387
388         EXAMPLES::
389
390             sage: H = HArrangement([[1,0,0],[0,1,1],[0,1,-1],[1,-1,0],[1,1,0]])
391             sage: H.hyperplanes()
392             [Hyperplane over Rational Field
393             (1, 0)*X = 0,
394              Hyperplane over Rational Field
395             (0, 1)*X = 1,
396              Hyperplane over Rational Field
397             (0, 1)*X = -1,
398              Hyperplane over Rational Field
399             (1, -1)*X = 0,
400              Hyperplane over Rational Field
401             (1, 1)*X = 0]
402         """
403         return copy(self._hyperplanes)
404
405     def cone(self):
406         r"""
407         NOTE: INCOMPLETE
408
409         INPUT:
410
411         - None
412
413         OUTPUT:
414
415         - hyperplane arrangement
416
417         EXAMPLES::
418
419             sage: HA.cone()
420             Hyperplane arrangement of 3 hyperplanes over Rational Field of dimension 3, rank 3.
421         """
422         hyps = []
423         for h in self.hyperplanes():
424             new = h.equation(suppress_printing=True)
425             new[-1] = -new[-1]
426             new.append(0)
427             hyps.append(new)
428         hyps.append([0]*self.dim()+[1,0])
429         return HArrangement(hyps,self.base_field())
430
431     def dim(self):
432         return self._dim
433
434     def _set_rank(self):
435         self._rank= matrix([list(H.normal()) for H in self._hyperplanes]).rank()
436
437     def rank(self):
438         return self._rank
439
440     def has_good_reduction(self,p):
441         raise UserWarning, 'not implemented'
442
443     def is_essential(self):
444         r"""
445         Indicates whether the hyperplane arrangement is essential. A hyperplane
446         arrangement is essential if the span of the normals of its hyperplanes
447         spans the ambient space.
448
449         INPUT:
450
451         - None
452
453         OUTPUT:
454
455         - boolean
456
457         EXAMPLES::
458
459             sage: HArrangement([[1,0,0],[1,0,1]]).is_essential()
460             False
461         """
462         r = matrix([list(H.normal()) for H in self._hyperplanes]).rank()
463         return r==self._dim
464
465     def _set_intersection_poset(self):
466         ## initiate with codim = 0, K^n
467         K = self.base_field()
468         Kn = AffSpace(vector(K,[0 for i in
469             range(self._dim)]),self._ambient_space)
470         L = [[Kn]]
471         active = True
472         codim = 0
473         while active:
474             active = False
475             new_level = []
476             for T in L[codim]:
477                 for H in self._hyperplanes:
478                     I = H.intersection(T)
479                     if type(I)!=type(-1) and I!=T and I not in new_level:
480                         new_level.append(I)
481                         active = True
482             if active:
483                 L.append(new_level)
484             codim += 1
485         L = flatten(L)
486         t = {}
487         for i in range(len(L)):
488             t[i] = L[i]
489         cmp_fn = lambda p,q: t[q]<t[p]
490         self._intersection_poset = Poset((t,cmp_fn))
491
492     def intersection_poset(self):
493         return deepcopy(self._intersection_poset)
494
495     def _set_characteristic_polynomial(self):
496         #P = self._intersection_poset
497         #n = self._dim
498         #self._characteristic_polynomial = sum([P.mobius_function(0,p)*x^(n-P.rank(p)) for p in P])
499         if self.rank()==1:
500             self._characteristic_polynomial = x^(self.dim()-1)*(x-self.num_hyperplanes())
501         else:
502             H = self.hyperplanes()[0]
503             R = self.restriction(H)
504             r = R.characteristic_polynomial()
505             D = self.deletion(H)
506             d = D.characteristic_polynomial()
507             self._characteristic_polynomial = expand(d - r)
508             return
509
510     def _set_poincare_polynomial(self):
511         p = (-x)^self.dim()*self.characteristic_polynomial(-1/x)
512         self._poincare_polynomial = expand(p)
513
514     def change_base_field(self):
515         raise UserWarning, 'not implemented'
516
517     def characteristic_polynomial(self,a=None):
518         if a==None:
519             return self._characteristic_polynomial
520         else:
521             return self._characteristic_polynomial.subs(x=a)
522
523     def poincare_polynomial(self,a=None):
524         if a==None:
525             return self._poincare_polynomial
526         else:
527             return self._poincare_polynomial.subs(x=a)
528
529     def num_bounded_regions(self):
530         r"""
531         Returns the number of (relatively) bounded regions of the hyperplane
532         arrangement as a subset of \mathbb{RR}.
533
534         INPUT:
535
536         - None
537
538         OUTPUT:
539
540         - integer
541
542         EXAMPLES::
543
544             sage: A = hyperplane_arrangements.semiorder(3)
545             sage: A.num_bounded_regions()
546             7
547         """
548         if self.base_field().characteristic()!=0:
549             raise UserWarning, 'base field must have characteristic zero'
550         return (-1)^self.rank()*self.characteristic_polynomial(1)
551
552     def num_regions(self):
553         r"""
554         Returns the number of regions of the hyperplane arrangement.
555
556         INPUT:
557
558         - None
559
560         OUTPUT:
561
562         - integer
563
564         EXAMPLES::
565
566             sage: A = hyperplane_arrangements.semiorder(3)
567             sage: A.num_regions()
568             19
569         """
570         if self.base_field().characteristic()!=0:
571             raise UserWarning, 'base field must have characteristic zero'
572         return (-1)^self._dim*self.characteristic_polynomial(-1)
573
574     def num_hyperplanes(self):
575         return len(self.hyperplanes())
576
577     def ambient_space(self):
578         r"""
579         The ambient space of the hyperplane arrangement.
580
581         INPUT:
582
583         - None
584
585         OUTPUT:
586
587         - vector space
588
589         EXAMPLES::
590
591             sage: A = HArrangement([[1,0,0],[0,1,1],[0,1,-1],[1,-1,0],[1,1,0]])
592             sage: A.ambient_space()
593             Vector space of dimension 2 over Rational Field
594         """
595         return deepcopy(self._ambient_space)
596
597     def base_field(self):
598         r"""
599         The base field of the hyperplane arrangement.
600
601         INPUT:
602
603         - None
604
605         OUTPUT:
606
607         - field
608
609         EXAMPLES::
610
611             sage: A = HArrangement([[1,0,0],[0,1,1],[0,1,-1],[1,-1,0],[1,1,0]])
612             sage: A.base_space()
613             Rational Field
614
615 	.. SEEALSO::
616
617 		:meth:.change_base_field
618         """
619         return self._base_field
620
621     def deletion(self,h):
622         r"""
623         The hyperplane arrangement obtained by deleting h from the hyperplane arrangement.
624
625         INPUT:
626
627         - h -- Hyperplane
628
629         OUTPUT:
630
631         - HArrangement
632
633         EXAMPLES::
634
635 	    sage: A = HArrangement([[1,0,0],[0,1,1],[0,1,-1],[1,-1,0],[1,1,0]])
636 	    sage: h = Hyperplane([1,0,0])
637 	    sage: A
638 	    Hyperplane arrangement of 5 hyperplanes over Rational Field of dimension 2, rank 2.
639 	    sage: A.deletion(h)
640 	    Hyperplane arrangement of 4 hyperplanes over Rational Field of dimension 2, rank 2.
641
642
643 	.. SEEALSO::
644
645 		:meth:.restriction
646         """
647         if h in self._hyperplanes:
648             A = [k.equation(True) for k in self.hyperplanes()]
649             A.remove(h._raw_data)
650             return HArrangement(A,self.base_field())
651         else:
652             raise UserWarning, 'hyperplane is not in the arrangement'
653
654     def _set_essentialization(self):
655         r"""
656         The essentialization of the hyperplane arrangement.  See the
657         documentation for essentialization.
658         """
659         if self.rank()==self.dim():
661         else:
662             n = [h.normal() for h in self._hyperplanes]
663             N = self.ambient_space().subspace(n)
664             # we need to be careful finding complementary spaces when the
665             # characteristic is not 0
666             if N.base_field().characteristic()!=0:
667                 m = N.echelonized_basis_matrix()
668                 c = [m.nonzero_positions_in_row(i)[0] for i in range(m.nrows())]
669                 new_basis = [self.ambient_space().basis()[i] for i in c]
670                 N = self.ambient_space().subspace(new_basis)
671             V = VectorSpace(self.base_field(),N.dimension())
672             N = AffSpace(vector([0]*self.dim()),N)
673             new_hyperplanes = []
674             for h in self.hyperplanes():
675                 I = h.intersection(N)
676                 basis = I.linear_part().matrix()
677                 p = N.isomorphism_with_Kn(I.point())
678                 new_basis = matrix(self.base_field(),[N.isomorphism_with_Kn(b) for b in basis])
679                 if new_basis.nrows()==0:
680                     eqn = [1,p[0]]
681                 else:
682                     eqn = new_basis.right_kernel_matrix()[0]
683                     q = [eqn*p]
684                     eqn = list(eqn)+q
685                 new_hyperplanes.append(eqn)
686             self._essentialization = HArrangement(new_hyperplanes,self.base_field())
687
688     def essentialization(self):
689         r"""
690         The essentialization of a hyperplane arrangement.  If the characteristic
691         of the base field is 0, this returns the hyperplane arrangement obtained
692         by intersecting the hyperplanes by the space spanned by their normal
693         vectors.
694
695         INPUT:
696
697         - None
698
699         OUTPUT:
700
701         - HArrangement
702
703         EXAMPLES::
704
705 	    sage: A = hyperplane_arrangements.braid(3)
706 	    sage: A.is_essential()
707 	    False
708 	    sage: A.essentialization()
709 	    Hyperplane arrangement of 3 hyperplanes over Rational Field of dimension 2, rank 2.
710 	    sage: B = HArrangement([[1,0,1],[1,0,-1]])
711 	    sage: B.is_essential()
712 	    False
713 	    sage: B.essentialization()
714 	    Hyperplane arrangement of 2 hyperplanes over Rational Field of dimension 1, rank 1.
715 	    sage: B.essentialization().hyperplanes()
716 	    [Hyperplane over Rational Field
717 	    (1)*X = 1,
718 	     Hyperplane over Rational Field
719 	    (1)*X = -1]
720             sage: C = HArrangement([[1,1,1],[1,1,0]],GF(2))
721             sage: C.essentialization().hyperplanes()
722             [Hyperplane over Finite Field of size 2
723             (1)*X = 1,
724              Hyperplane over Finite Field of size 2
725             (1)*X = 0]
726         """
727         return self._essentialization
728
729     def polytope(self):
730         if self._from_polytope:
731             return deepcopy(self._polytope)
732
733     def _set_regions(self):
734         r"""
735         Computes the regions of the hyperplane arrangement.  See the
736         documentation for regions.
737         """
738         if self.base_field().characteristic()!=0:
739             raise UserWarning, 'base field must have characteristic zero'
740         result = []
741         num = self.num_hyperplanes()
742         h = [i.equation(suppress_printing=True) for i in self.hyperplanes()]
743         for pos in powerset(range(num)):
744             q = []
745             for i in range(num):
746                 if i in pos:
747                     new = [-h[i][-1]]+h[i][:-1]
748                     q.append(new)
749                 else:
750                     new = [h[i][-1]]+[-t for t in h[i][:-1]]
751                     q.append(new)
752             P = Polyhedron(ieqs=q)
753             if P.dim()==self.dim():
754                 result.append(P)
755         self._regions = result
756
757     def regions(self):
758         r"""
759         The regions of the hyperplane arrangement, i.e., the connected components of the
760         complement of the union of the hyperplanes as a subset of \mathbb{R}^n.
761
762         INPUT:
763
764         - None
765
766         OUTPUT:
767
768         - a list of polyhedra
769
770         EXAMPLES::
771
772             sage: A = HArrangement([[1,0,0],[0,1,1]])
773             sage: A.regions()
774             [[A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 2 rays],
775             [A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 2 rays],
776             [A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 2 rays],
777             [A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 2 rays]]
778         """
779         return self._regions
780
781     def region_containing_point(self,p):
782         r"""
783         The region in the hyperplane arrangement containing a given point.
784
785         INPUT:
786
787         - a point
788
789         OUTPUT:
790
791         - a polyhedron
792
793         EXAMPLES::
794
795             sage: A = HArrangement([[1,0,0],[0,1,1],[0,1,-1],[1,-1,0],[1,1,0]])
796             sage: A.region_containing_point((1,2))
797             A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 2 rays
798         """
799         if self.base_field().characteristic()!=0:
800             raise UserWarning, 'base field must have characteristic zero'
801         h = [i.equation(suppress_printing=True) for i in self.hyperplanes()]
802         q = []
803         sign_vector = self.sign_vector(p)
804         if 0 in sign_vector:
805             raise UserWarning, 'point sits on a hyperplane'
806             return
807         for i in range(self.num_hyperplanes()):
808             if sign_vector[i]==1:
809                 new = [-h[i][-1]]+h[i][:-1]
810                 q.append(new)
811             else:
812                 new = [h[i][-1]]+[-t for t in h[i][:-1]]
813                 q.append(new)
814         return Polyhedron(ieqs=q)
815
816     def sign_vector(self,p):
817         r"""
818         Sign_vector indicates on which side of each hyperplane the given point p lies.
819
820         INPUT:
821
822         - point
823
824         OUTPUT:
825
826         - vector
827
828         EXAMPLES::
829
830             sage: A = HArrangement([[1,0,0],[0,1,1]])
831             sage: A.sign_vector((2,-2))
832             [1, -1]
833             A.sign_vector((1,1))
834             [1, 0]
835         """
836         if self.base_field().characteristic()!=0:
837             raise UserWarning, 'characteristic must be zero'
838         else:
839             p = vector(p)
840             eqns = [i.equation(suppress_printing=True) for i in self.hyperplanes()]
841             return [sign(p*vector(e[:-1])-e[-1]) for e in eqns]
842
843     def restriction(self,H):
844         r"""
845         The restriction of the hyperplane arrangement to the given hyperplane, H.
846         This is obtained by intersecting  H with all of the other distinct
847         hyperplanes.  The hyperplane H must be in the arrangement.
848
849
850         INPUT:
851
852         - a Hyperplane
853
854         OUTPUT:
855
856         - an HArrangement
857
858         EXAMPLES::
859
860 	    sage: A = hyperplane_arrangements.braid(4)
861 	    sage: H = A.hyperplanes()[0]
862 	    sage: H
863 	    Hyperplane over Rational Field
864 	    (1, -1, 0, 0)*X = 0
865 	    sage: R = A.restriction(H)
866 	    sage: D = A.deletion(H)
867 	    sage: ca = A.characteristic_polynomial()
868 	    sage: cr = R.characteristic_polynomial()
869 	    sage: cd = D.characteristic_polynomial()
870 	    sage: ca
871 	    x^4 - 6*x^3 + 11*x^2 - 6*x
872 	    sage: cd - cr
873 	    x^4 - 6*x^3 + 11*x^2 - 6*x
874
875 	.. SEEALSO::
876
877 		:meth:.deletion
878         """
879         if H not in self.hyperplanes():
880             raise UserWarning, 'hyperplane not in arrangement'
881         else:
882             new_hyperplanes = []
883             for T in self.hyperplanes():
884                 if T!=H:
885                     I = H.intersection(T)
886                     if type(I)!=Integer and I not in new_hyperplanes:
887                         new_hyperplanes.append(I)
888         final_hyperplanes = []
889         for T in new_hyperplanes:
890             basis = T.linear_part().matrix()
891             p = H.isomorphism_with_Kn(T.point())
892             if basis.nrows()==0:
893                 eqn = [1] + list(p)
894             else:
895                 new_basis = matrix(self.base_field(),[H.isomorphism_with_Kn(b+H.point())
896                     for b in basis])
897                 eqn = new_basis.right_kernel_matrix()[0]
898                 q = list(eqn*p)
899                 eqn = list(eqn)+q
900             final_hyperplanes.append(eqn)
901         return HArrangement(final_hyperplanes,self.base_field())
902
903     def show(self,r=None,**kwds):
904         if r==None:
905             r = 1
906         if self.dim()==2 or self.dim()==3: # so the dimension of the ambient space is 3
907             sum([h.plot(r) for h in self.hyperplanes()]).show(**kwds)
908
909     def union(self,A):
910         r"""
911         The union of one HArrangement with another.
912
913         INPUT:
914
915         - A -- HArrangement
916
917         OUTPUT:
918
919         - HArrangement
920
921         EXAMPLES::
922
923             sage: A = HArrangement([[1,0,0],[0,1,1],[0,1,-1],[1,-1,0],[1,1,0]])
924             sage: B = HArrangement([[1,1,1],[1,-1,1],[1,0,-1]])
925             sage: A.union(B)
926 	    Hyperplane arrangement of 8 hyperplanes over Rational Field of dimension 2, rank 2.
927         """
928         hyps = [i.equation(true) for i in self.hyperplanes()] + [i.equation(true)
929                 for i in A.hyperplanes()]
930         return HArrangement(hyps,self.base_field())
931
932 # Idea: calculate characteristic polynomials and set
933 # self._characteristic_polynomial while constructing the special hyperplane
934 # arrangement.  Also set poset?
935 class HArrangementGenerators():
936
937     def semiorder(self,n,K=QQ):
938         r"""
939         The semiorder arrangement is the set of n(n-1) hyperplanes: \{ x_i - x_j = -1,1 : 1\leq i \leq j\leq n\}.
940
941         INPUT:
942
943         - n -- integer
944         - K (default QQ)
945
946         OUTPUT:
947
948         - HArrangement
949
950         EXAMPLES::
951
952             sage: hyperplane_arrangements.semiorder(4)
953             Hyperplane arrangement of 12 hyperplanes over Rational Field of dimension 4, rank 3.
954         """
955         hyperplanes = []
956         for i in range(n):
957             for j in range(i+1,n):
958                 new = [0]*n
959                 new[i] = 1
960                 new[j] = -1
961                 for k in [-1,1]:
962                     h = deepcopy(new)
963                     h.append(k)
964                     hyperplanes.append(h)
965         return HArrangement(hyperplanes,K)
966
967     def Shi(self,n,K=QQ):
968         r"""
969         The Shi arrangement is the set of n(n-1) hyperplanes: \{ x_i - x_j = 0,1 : 1\leq i \leq j\leq n\}.
970
971         INPUT:
972
973         - n -- integer
974
975         OUTPUT:
976
977         - HArrangement
978
979         EXAMPLES::
980
981             sage: hyperplane_arrangements.Shi(4)
982             Hyperplane arrangement of 12 hyperplanes over Rational Field of dimension 4, rank 3.
983         """
984         hyperplanes = []
985         for i in range(n):
986             for j in range(i+1,n):
987                 new = [0]*n
988                 new[i] = 1
989                 new[j] = -1
990                 for k in [0,1]:
991                     h = deepcopy(new)
992                     h.append(k)
993                     hyperplanes.append(h)
994         return HArrangement(hyperplanes,K)
995
996     def Catalan(self,n,K=QQ):
997         r"""
998         The Catalan arrangement is the set of 3n(n-1)/2 hyperplanes: \{ x_i - x_j = -1,0,1 : 1\leq i \leq j\leq n\\}.
999
1000         INPUT:
1001
1002         - n -- integer
1003
1004         OUTPUT:
1005
1006         - HArrangement
1007
1008         EXAMPLES::
1009
1010             sage: hyperplane_arrangements.Catalan(5)
1011             Hyperplane arrangement of 30 hyperplanes over Rational Field of dimension 5, rank 4.
1012         """
1013         hyperplanes = []
1014         for i in range(n):
1015             for j in range(i+1,n):
1016                 new = [0]*n
1017                 new[i] = 1
1018                 new[j] = -1
1019                 for k in [-1,0,1]:
1020                     h = deepcopy(new)
1021                     h.append(k)
1022                     hyperplanes.append(h)
1023         Cn = HArrangement(hyperplanes,K)
1024         Cn._characteristic_polynomial = expand(x*prod([x-n-i for i in range(1,n)]))
1025         return Cn
1026
1027     def coordinate(self,n,K=QQ):
1028         r"""
1029         The coordinate hyperplane arrangement is the central hyperplane arrangement consisting of the coordinate hyperplanes x_i=0.
1030
1031         INPUT:
1032
1033         - n -- integer
1034
1035         OUTPUT:
1036
1037         - HArrangement
1038
1039         EXAMPLES::
1040
1041             sage: hyperplane_arrangements.coordinate(5)
1042             Hyperplane arrangement of 5 hyperplanes over Rational Field of dimension 5, rank 5.
1043         """
1044         hyperplanes = []
1045         for i in range(n):
1046             new = [0]*(n+1)
1047             new[i]=1
1048             hyperplanes.append(new)
1049         return HArrangement(hyperplanes,K)
1050
1051     def graphical(self,G,K=QQ):
1052         hyperplanes = []
1053         n = G.num_verts()
1054         for e in G.edges():
1055             i = G.vertices().index(e[0])
1056             j = G.vertices().index(e[1])
1057             new = [0]*(n+1)
1058             new[i] = 1
1059             new[j] = -1
1060             hyperplanes.append(new)
1061         A = HArrangement(hyperplanes,K)
1062         A._characteristic_polynomial = G.chromatic_polynomial()
1063         return A
1064
1065     def braid(self,n,K=QQ):
1066         r"""
1067         The braid arrangement is the set of n(n-1)/2 hyperplanes: \{ x_i - x_j = 0 : 1\leq i \leq j\leq n\\}.
1068
1069         INPUT:
1070
1071         - n integer
1072
1073         OUTPUT:
1074
1075         - HArrangement
1076
1077         EXAMPLES::
1078
1079             sage: hyperplane_arrangements.braid(4)
1080             Hyperplane arrangement of 6 hyperplanes over Rational Field of dimension 4, rank 3.
1081         """
1082         A = self.graphical(graphs.CompleteGraph(n),K)
1083         A._characteristic_polynomial = expand(prod(x-i for i in range(n)))
1084         return A
1085
1086     def G_Shi(self,G,K=QQ):
1087         hyperplanes = []
1088         n = G.num_verts()
1089         for e in G.edges():
1090             i = G.vertices().index(e[0])
1091             j = G.vertices().index(e[1])
1092             new = [0]*(n+1)
1093             new[i] = 1
1094             new[j] = -1
1095             hyperplanes.append(new)
1096             new = deepcopy(new)
1097             new[-1]=1
1098             hyperplanes.append(new)
1099         return HArrangement(hyperplanes,K)
1100
1101     def G_semiorder(self,G,K=QQ):
1102         hyperplanes = []
1103         n = G.num_verts()
1104         for e in G.edges():
1105             i = G.vertices().index(e[0])
1106             j = G.vertices().index(e[1])
1107             new = [0]*(n+1)
1108             new[i] = 1
1109             new[j] = -1
1110             new[-1] = -1
1111             hyperplanes.append(new)
1112             new = deepcopy(new)
1113             new[-1]=1
1114             hyperplanes.append(new)
1115         return HArrangement(hyperplanes,K)
1116
1117     def G_arrangement(self,G,A=None,K=QQ):
1118         r"""
1119         A - None (semiorder), 'generic'
1120         """
1121         n = G.num_verts()
1122         if A==None:  #default to G-semiorder arrangement
1123             A = matrix(K,n,lambda i,j: 1)
1124         elif A=='generic':
1125             A = random_matrix(ZZ,n,x=10000)
1126             A = matrix(K,A)
1127         hyperplanes = []
1128         for e in G.edges():
1129             i = G.vertices().index(e[0])
1130             j = G.vertices().index(e[1])
1131             new = [0]*(n+1)
1132             new[i] = 1
1133             new[j] = -1
1134             new[-1] = A[i,j]
1135             hyperplanes.append(new)
1136             new = [0]*(n+1)
1137             new[j] = 1
1138             new[i] = -1
1139             new[-1] = A[j,i]
1140             hyperplanes.append(new)
1141         return HArrangement(hyperplanes,K)
1142
1143 hyperplane_arrangements = HArrangementGenerators()
1144 harrangements = HArrangementGenerators()
1145
1146 # idea: store information about some of these hyperplanes
1147
1148 def repr_point(P,scale=1):
1149     c = P.center()
1150     if P.n_rays()==0:
1151         return c
1152     else:
1153         r = sum([vector(QQ,i) for i in P.rays()])
1154         return c + scale*r/r.norm()


## Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.
• [get | view] (2013-06-26 21:28:48, 210.2 KB) [[attachment:CombinatoricsReference.pdf]]
• [get | view] (2013-06-26 21:29:08, 8.1 KB) [[attachment:CombinatoricsReference.tex]]
• [get | view] (2013-06-21 00:20:24, 485.4 KB) [[attachment:DavisSlides.pdf]]
• [get | view] (2013-06-20 20:45:29, 105.7 KB) [[attachment:InteractQuickstart.sws]]
• [get | view] (2013-06-20 21:02:40, 27.6 KB) [[attachment:MV-Calculus-Interacts.zip]]
• [get | view] (2013-06-19 18:17:22, 2.4 KB) [[attachment:MyDemo.html]]
• [get | view] (2013-06-19 18:17:29, 1.4 KB) [[attachment:MyTalk.rtf]]
• [get | view] (2013-06-21 22:51:37, 437.8 KB) [[attachment:PerkinsonSageEdu5.pdf]]
• [get | view] (2013-06-21 17:57:43, 107.0 KB) [[attachment:SAGETalk-Balof.pdf]]
• [get | view] (2013-06-20 23:40:21, 1004.5 KB) [[attachment:SALG_MSageInstrument.pptx]]
• [get | view] (2013-06-20 23:40:03, 105.4 KB) [[attachment:SALG_M_Invitation.pdf]]
• [get | view] (2013-06-18 16:53:39, 15.5 KB) [[attachment:Sage-Days-5-Reimbursement-Form.pdf]]
• [get | view] (2013-06-20 18:24:15, 103.1 KB) [[attachment:SageEduDennytalk.pdf]]
• [get | view] (2013-06-20 23:39:53, 449.4 KB) [[attachment:SageSALG_MDirections.pdf]]
• [get | view] (2013-06-20 00:14:20, 42.7 KB) [[attachment:WednesdayGroupSansTravis.jpg]]
• [get | view] (2013-06-21 22:52:11, 32.7 KB) [[attachment:hyperplane.sage]]
• [get | view] (2013-06-21 17:27:39, 263.7 KB) [[attachment:sage-edu-days-5-uw-20130619.jpg]]
• [get | view] (2013-06-21 17:37:31, 286.5 KB) [[attachment:sage-edu-days-5-uw-20130621.jpg]]
All files | Selected Files: delete move to page copy to page