Essays/Block Matrix Inverse
Block Matrix
A block matrix is a partition of the rows and columns of a matrix; in general, a block array is a partition of each dimension of the array. For example:
] xx=: i. 5 6 0 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 ] yy=: (1 0 1 0 0 ; 1 0 0 1 1 0) <;.1 xx ┌────────┬──┬─────┐ │0 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│ └────────┴──┴─────┘
As the example indicates, a block matrix can be created using the cut <;.1 with a left argument of boxed boolean vectors, with 1s marking the starts of partitions. (It can also be created using <;.2 with the 1s in the boolean vectors indicating the ends of the partitions.)
The rest of the essay will also use the following somewhat bigger example:
x=: 5 7 6 8 ?.@$ 1e6 p=: (i.&.>$x) e.&.> 0,&.>3 ?.@$&.>$x y=: p <;.1 x p ┌─────────┬─────────────┬───────────┬───────────────┐ │1 1 0 0 1│1 0 0 1 0 0 1│1 0 0 0 0 1│1 0 1 1 0 0 0 1│ └─────────┴─────────────┴───────────┴───────────────┘ $y 3 3 2 4
Block Matrix Inverse
The inverse operation, obtaining a matrix from a block matrix (an array from a block array), can be effected by <;.1^:_1 or <;.2^:_1 , modelled as follows:
binv0=: 3 : 0
z=. y
for_r. (-i.) #$y do. z=. ,"r&.>/z end.
> z
)
binv1=: [: > 3 : ',"(#$y)&.>/y'^:(#@$)
binv2=: 3 : 0
r=. #$y
c=. (\:"1 =i.r) <@(''&($,)"_1)@|:"_1 >&.|: $&.>y
s=. +/&> c
p=. (i.&.>s) e.&.> +/\@(0&,)&.> c
s $ y /:&(;@:(,&.>)) p <;.1 i.s
)
binv0 and binv1 implement the following idea:
t=: y t=: ,"4&.>/ t t=: ,"3&.>/ t t=: ,"2&.>/ t t=: ,"1&.>/ t x -: >t 1 x -: binv0 y 1 x -: binv1 y 1
binv2 is a step-by-step re-creation of the parts needed to create y from x in the first place. c are the partition lengths in each dimension. s is the shape of the original array. p are the partition vectors.
The values of the local names in binv2 when it is applied to y :
r 4 c ┌─────┬─────┬───┬───────┐ │1 3 1│3 3 1│5 1│2 1 4 1│ └─────┴─────┴───┴───────┘ s 5 7 6 8 p ┌─────────┬─────────────┬───────────┬───────────────┐ │1 1 0 0 1│1 0 0 1 0 0 1│1 0 0 0 0 1│1 0 1 1 0 0 0 1│ └─────────┴─────────────┴───────────┴───────────────┘ x -: binv2 y 1
An Extension
The actual inverses of <;.1 and <;.2 permit the following extension: Each block may be a scalar or vector, which is reshaped to a diagonal array with the right shape.
bi=: 3 : 0
ry=. #$y
assert. 1 < ry
assert. 32=3!:0 y
d=. len y
c=. >./"1&.> d
assert. ; ,&.> c (= +. _1&=@])&.>d
j=. I. , ry > #@$&> y
t=. y j"_}~ (j{,{c) diag&.> j{,y
> 3 : ',"(#$y)&.>/y'^:ry t
)
diag=: 4 : 0
assert. (0=#$y) +. (<./x)=#y
y ((#x) #&.> i.<./x)} x$0
)
len=: 3 : 0
ry=. #$y
r=. #&> s=. $&.> y
assert. r e. 0 1,ry
assert. ((-i.)ry) 4 : '*./,+./"x y'"0 _ *r
(\:"1 =i.ry) <@,.@|:"_1 >&.|: (ry>r)}s,:<ry$_1
)
bi models the (extended) inverse of <;.1 and <;.2 . s diag y creates an array of shape s with scalar or vector y as the diagonal entries. len y computes the lengths of each block in each dimension.
Examples:
4 4 diag 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 3 3 5 diag 99 88 77 99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 88 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 77 0 0 yy ┌────────┬──┬─────┐ │0 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│ └────────┴──┴─────┘ len yy ┌─────┬───┐ │2 2 2│3 3│ │3 3 3│1 1│ │ │2 2│ └─────┴───┘ <./"1&.> len yy ┌───┬─────┐ │2 3│3 1 2│ └───┴─────┘ bi yy 0 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 ] y1=: (<1) (<1 0)}yy ┌─────┬──┬─────┐ │0 1 2│3 │ 4 5│ │6 7 8│9 │10 11│ ├─────┼──┼─────┤ │1 │15│16 17│ │ │21│22 23│ │ │27│28 29│ └─────┴──┴─────┘ bi y1 0 1 2 3 4 5 6 7 8 9 10 11 1 0 0 15 16 17 0 1 0 21 22 23 0 0 1 27 28 29 ] y2=: (<88 99) (<1 2)}yy ┌────────┬──┬─────┐ │0 1 2 │3 │ 4 5│ │6 7 8 │9 │10 11│ ├────────┼──┼─────┤ │12 13 14│15│88 99│ │18 19 20│21│ │ │24 25 26│27│ │ └────────┴──┴─────┘ bi y2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 88 0 18 19 20 21 0 99 24 25 26 27 0 0
See also
- Cholesky Decomposition
- LU Decomposition
- QR Decomposition
- Matrix Inverse
- Triangular Matrix Inverse
- Determinant
- Minors
- Hilbert Matrix
- Block Matrix Inverse
- Kronecker Product
Contributed by Roger Hui.