limit and closure

[Roger|Dyalog]

Let f be an associative function with an identity item. ⍺ ∘.f ⍵ computes the function table for ⍺ versus ⍵ and ∪,∘.f⍨⍵ are the unique items of ⍵ against itself. If ⍵ is prefaced by the identity item ⍺, then ∪∘,∘(∘.f⍨)⍣≡⍺⍪⍵ is the closure of ⍵ under f. That is, augmenting by the identity converts a limit computation into a closure computation, and can be written as follows:

      C←{∪∘,∘(∘.⍺⍺⍨)⍣≡⍺⍪⍵}

(The ⍣≡ would not terminate if the closure is not finite or if an incorrect identity item is specified.)

In group theory, ⍺ f C ⍵ is the subgroup generated by ⍵.

Example: Addition and multiplication modulo 7

      0 (7|+) C 1
0 1 2 3 4 5 6

      1 (7|×) C 1
1
      1 (7|×) C 2
1 2 4
      1 (7|×) C 2 3
1 2 3 4 6 5

Example: Permutations

      (⊂⍳4) {⍵[⍺]}C ⊂1 2 3 0
┌───────┬───────┬───────┬───────┐
│0 1 2 3│1 2 3 0│2 3 0 1│3 0 1 2│
└───────┴───────┴───────┴───────┘
      (⊂⍳4) {⍵[⍺]}C ⊂1 0 2 3
┌───────┬───────┐
│0 1 2 3│1 0 2 3│
└───────┴───────┘
      (⊂⍳4) {⍵[⍺]}C (⊂1 2 3 0),⊂1 0 2 3
┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬   ┬───────┬───────┐
│0 1 2 3│1 2 3 0│1 0 2 3│2 3 0 1│0 2 3 1│2 1 3 0│3 0 1 2│ … │1 2 0 3│1 0 3 2│
└───────┴───────┴───────┴───────┴───────┴───────┴───────┴   ┴───────┴───────┘
      ⍴ (⊂⍳4) {⍵[⍺]}C (⊂1 2 3 0),⊂1 0 2 3
24

      gen←{(⊂1⊖⍳⍵),(1<⍵)⍴⊂1 0,2↓⍳⍵}
      gen¨ ⍳7
┌──┬───┬─────┬─────────────┬─────────────────┬─────────────────────┬─────────────────────────┐
│┌┐│┌─┐│┌───┐│┌─────┬─────┐│┌───────┬───────┐│┌─────────┬─────────┐│┌───────────┬───────────┐│
│││││0│││1 0│││1 2 0│1 0 2│││1 2 3 0│1 0 2 3│││1 2 3 4 0│1 0 2 3 4│││1 2 3 4 5 0│1 0 2 3 4 5││
│└┘│└─┘│└───┘│└─────┴─────┘│└───────┴───────┘│└─────────┴─────────┘│└───────────┴───────────┘│
└──┴───┴─────┴─────────────┴─────────────────┴─────────────────────┴─────────────────────────┘

      ≢∘{(⊂⍳⍵) {⍵[⍺]}C gen ⍵}¨ ⍳7 
1 1 2 6 24 120 720
      ! ⍳7
1 1 2 6 24 120 720

(Misalignments in the display are due to defects in the APL Chat Forum software.)

That is, gen ⍵ (≤ 2 permutations) suffice to generate the group of permutations of order ⍵. See I.N. Herstein, Topics in Algebra, Second Edition, Xerox College Publishing, 1975, exercise 2.10.11.

Example: Non-singular boolean matrices

      x← ⊂⍤2 ⊢2 2 ⍴⍤1 ⍉(4⍴2)⊤⍳16
      ⍴x
16
      )copy dfns det

      ⊢ x←(0≠det¨ x)⌿x
┌───┬───┬───┬───┬───┬───┐
│0 1│0 1│1 0│1 0│1 1│1 1│
│1 0│1 1│0 1│1 1│0 1│1 0│
└───┴───┴───┴───┴───┴───┘
      (⊂2 2⍴1 0 0 1) ≠.∧ C x[0]
┌───┬───┐
│1 0│0 1│
│0 1│1 0│
└───┴───┘
      (⊂2 2⍴1 0 0 1) ≠.∧ C x[0 1]
┌───┬───┬───┬───┬───┬───┐
│1 0│0 1│0 1│1 1│1 0│1 1│
│0 1│1 0│1 1│0 1│1 1│1 0│
└───┴───┴───┴───┴───┴───┘

Aside: Ken Iverson [Iverson 2008, §5] credits Linda Alvord with the observation that ∘.f is the function table for f, such as the addition table or multiplication table familiar to students of elementary grades. Function tables also provide an easier and less intimidating introduction to matrices. In contrast, outer product and matrices are commonly not encountered until university-level mathematics.

[Roger|Dyalog]

That is, augmenting by the identity converts a limit computation into a closure computation, and can be written as follows:

      C←{∪∘,∘(∘.⍺⍺⍨)⍣≡⍺⍪⍵}

(The ⍣≡ would not terminate if the closure is not finite or if an incorrect identity item is specified.)

It is possible to use power limit ⍣≡ to compute the closure without the identity, by catenating the argument from each iteration:

      C←{                        
        0=⎕nc'⍺': (∪ ⊢ ⍪ (, ∘.⍺⍺⍨))⍣≡⍵
        ∪∘,∘(∘.⍺⍺⍨)⍣≡⍺⍪⍵         
      }

For example:

      (7|+) C 1
1 2 3 4 5 6 0
      0 (7|+) C 1
0 1 2 3 4 5 6

      (7|×) C 2
2 4 1
      (7|×) C 6
6 1
      (7|×) C 2 6
2 6 4 5 1 3
      1 (7|×) C 2 6
1 2 6 4 5 3

      {⍵[⍺]} C ⊂1 2 3 0
┌───────┬───────┬───────┬───────┐
│1 2 3 0│2 3 0 1│3 0 1 2│0 1 2 3│
└───────┴───────┴───────┴───────┘
      (⊂⍳4) {⍵[⍺]} C ⊂1 2 3 0
┌───────┬───────┬───────┬───────┐
│0 1 2 3│1 2 3 0│2 3 0 1│3 0 1 2│
└───────┴───────┴───────┴───────┘

(Misalignments in the display are due to defects in the APL Chat Forum software.)

I note that the “catenating the argument” and the ⍺⍺⍨ constructs with ⍣ were used in the RS operator in the recent Repeated Squaring post:

      RS← {⊃ ⍺⍺⌿ b⌿ (⊢,⊂∘(⍺⍺⍨)∘⊃∘⊖)⍣(¯1+≢b) ⊂⍺ ⊣ b←⊖2⊥⍣¯1⊢⍵}