limit and closure

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !

limit and closure

Postby Roger|Dyalog on Thu May 21, 2020 6:08 pm

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
 
Posts: 208
Joined: Thu Jul 28, 2011 10:53 am

Re: limit and closure

Postby Roger|Dyalog on Fri May 22, 2020 1:01 pm

Roger|Dyalog wrote: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⊢⍵}
Roger|Dyalog
 
Posts: 208
Joined: Thu Jul 28, 2011 10:53 am


Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest