The Setting
An ordered matrix construction specifies a carrier for both axes and a separate order on each axis. Here the variable positions follow a complete binary tree, while anchor positions and dummy positions supply the other blocks of the matrix.
Fix a nonnegative integer , put and , and, for every nonnegative integer , write , with . All coordinates start at zero.
The Claim
Definition 1 (Tree positions and axis orders). The set of modes is the finite ordered set in (1). (1)✦ A mode has level and type . At each level, types are called , respectively.
A variable position is a pair in the set of (2); is its class and its coordinate. (2) The sign of a variable position in is when is even and when is odd. The depth and node index of a variable position in are the nonnegative integers defined by (3) and (4). (3)✦ (4)✦ For a nonnegative integer and a sign , the signed level is the subset of variable positions specified in (5). (5)✦ For a nonnegative integer , a sign and , the parity class of the signed level is the subset .
The anchor set is the set of triples consisting of a mode, an anchor group and a coordinate, as in (6). (6) The dummy positions form a separate copy of . The matrix carrier is the disjoint union in (7). (7)✦ The matrix size is the cardinality of the carrier , given by (8). (8)✦
For a mode of level and type , its first and second row roles are defined by (9). (9)✦ For a mode of level and type , the first and second column roles are defined by (10). (10)✦
A traversal key is a five-tuple of nonnegative integers, compared lexicographically, where selects the row axis and the column axis. For , put , and ; the leaf, subtree entry and subtree exit keys are the cases of (11). (11)✦ The variable order for each axis compares its traversal keys.✦
The anchor order compares mode, group and coordinate lexicographically.✦ Writing for an anchor in and for a dummy in , the row coordinate map and column coordinate map on are the maps defined by (12); the leading coordinate orders the blocks, and subsequent coordinates are compared lexicographically. (12) The row order on is defined by (13). (13)✦ For columns, (14) defines the order on . (14)✦ The increasing row enumeration is the bijection in (15). (15)✦ Counting column predecessors gives the increasing bijection in (16). (16)✦
In the paper, the result reads: for and , each internal node at depth has separate row blocks and column blocks of size , the two signs share singleton leaf blocks, each axis has a dummy block or of size , the variable row order is minus block, child subtree, child subtree, plus block and the column order reverses the signs, dummy rows follow all variable rows and dummy columns precede all variable columns, the modes at each depth occur in the order with respective row and column role quadruples , , and for , where subscript restricts node indices to parity , each mode has consecutive anchor groups of size on each axis placed before every non-anchor position in mode order, the total axis size is , and ordered bodies satisfy the row and column inequalities within their role sets.
What Is Checked
The definitions are stated for every nonnegative integer , on the finite carrier with its separate row and column orders and their increasing enumerations. For either axis, distinct variable positions have distinct traversal keys.✦