Transitional Matrices of Binary Remainders
Transitional Matrices of Binary Remainders [Cyclic Quality]. [The following is research, but since this is essentially elementary mathematics, the content of this contribution may be considered as self-validating.] The matrices represent uneven integers exclusively. Even integers cannot be represented by matrices of binary remainders. All the matrices involved are all square and non-singular. Given that Q = [2.n - 1] and the integer [n] takes values: [1, 2, ... ], Q in explicit binary has digits b[j] as coefficients of two [2] raised to ascending exponents: [0, 1, ... N] and of course, b[0] = 1 and b[N] = 1. [Implicit binary suppresses the exponents of two. Thus 13 Decimal is 1101 in implicit Binary.] The integer N takes values: [1, 2, ... ] Binary remainders derive from the division algorithm with divisor two [2], where an uneven integer, Q upon division by two produces a quotient that is an uneven integer, provided that the remainder, [r] is given by: r = i^{1 + Q}, where [i] satisfies: i^{2} = - 1 Iteration of this division process produces a series of remainders that are either + 1 or - 1. It is found that the binary digits representing Q are isomorphic to the binary remainders, where the iteration starts with r[N - 1] and ends with r[0]. By analogy, r[N] = 1 corresponding to b[0] = 1 and r[0] = 1 corresponding to b[N] = 1 Given that Q is positive, binary digit 1 maps to binary remainder + 1 and binary digit 0 maps to binary remainder - 1. Given that Q is negative, binary digit - 1 maps to binary remainder - 1 and binary digit 0 maps to binary remainder + 1. The integer Q is identifiable with Q[n, N] and Q[N]. An instance of the division algorithm in this case is: Q[n, N] = 2.Q[N - 1] + i^{1 + Q[n, N]} This is re-arranged below to give Q[N - 1] in terms of Q[N]. The final iteration is: Q[1] = 2.Q[0] + r[0] We invariably find that Q[1] = 3 and Q[0] = 1.
The uneven integer: Q[n, N] may be redefined as: Q[N, j] = 2^{N} - 1 + 2.j, where the integer N defines the inequalities: 2^{N} < Q[N, j] < 2^{N + 1} and j runs: [1, ... [2^{N - 1}]]. For the present purpose, the integer: [j] is to be considered as fixed in each succession of transitional matrices of remainders.
The matrix of binary digits is then B[N, Q[N, j], k]. The inequalities: 2^{N} < Q[N, j] < 2^{N + 1} set lower and upper limits on [n]. The integer: k runs: [1, ... [N + 1]] The smallest matrix of binary digits is B[1, 3, 1] having N = 1 and j = 1, representing Q[1, 1] = 3.
B[1, 3, 1]] is: 2 1
0 1
The first row [2 1] represents 3 in explicit binary and the last [second] row [0 1] represents 1 in explicit binary.
The successive rows of B are found from the explicit binary forms of the integers: Q[N, j]], Q[N - 1], Q[N - 2], ... Q[0] The first row is given by: Q[N, j] = 2.n - 1 = 2^{N} - 1 + 2.j as above. The second row by Q[N - 1] = [1/2].[Q[N, j] - i^{1 + Q[N, j]}] The third row is given by: Q[N - 2] = [1/2].[Q[N - 1] - i^{1 + Q[N - 1]}] et c. The last row, Q[0] = 1. In B[1, 3, 1], to find the first matrix of binary remainders, in the last row, the zero is replaced by minus two, recalling the isomorphic mapping above of binary digits to binary remainders. The general matrix of binary remainders may be designated as: D[N, Q[n, j], k] . The integer [k] runs: [1, 2, ... [N]] The first matrix of binary remainders then is: 2 1 This is D[1, 3, 1]
- 2 1
Generally, if the first matrix of binary remainders is D[N, Q[N, j], 1], followed by D[N, Q[N, j], 2] up to D[N, Q[N, j], [N + 1]], these being the [N + 1]transitional matrices. The successor matrix is related to its antecedent by: A[N, Q[N, j]].D[N,Q[N, j], k] = D[N, Q[N, j],[k + 1]] The integer [k] takes values [1, ... N] We can write: A[N, Q[N, j]].D[N, Q[N, j], [N + 1]] = D[N, Q[N, j], 1] This is the cyclic quality of the transitional matrices of remainders. In the example below, A[2, 5] representing Q[2, 1] = 5, A[2, 5] is same for the three resulting transitional matrices of remainders, hence no distinguishing subscript is needed in the description of the matrix A. Returning to the example, B[1, 3, 1], the algebraic sum of the successive rows of D[1, 3, 1], written as a row in decimal is: [3, - 1]. The successive elements of the decimal row [vector] are written as rows of a matrix B[1, 3, 2] of binary digits: 2 1
0 - 1
Taking the successive rows of B[1, 3, 2] and replacing the zero in the last row by 2, by the mapping process above, the matrix D[1, 3, 2] is
D[1, 3, 2] is 2 1
2 - 1
D[1, 3, 2] is the principal matrix of binary remainders. In general D[N, Q[N, j],[N + 1]] is the principal matrix of binary remainders in that the algebraic sums of the successive rows is identical to the corresponding algebraic sums in the primitive[starting] matrix of binary digits, B[N, Q[N, j], 1]. There are in fact only two transitional matrices of binary digits in the case of Q[1, 1], the first transitional matrix of binary digits would be B[1, 3, 1] and its successor, B[1, 3, 2]. We find that by solving for the elements of A[1, 3] in the matrix equation: A[1, 3].D[1, 3, 1] = D[1, 3, 2] that A[2, 1] is: 1 0
0 - 1
We find that: A[1, 3].D{1, 3, 2] = D[2, 1, 1] where the same matrix A indicates a cyclic quality.
The next case is Q[2, 1] = 5.
Starting from B[2, 5, 1] which is:
4 0 1
0 2 1
0 0 1
Using the prescribed mappings, the successor matrix D[2, 5, 1] is found, being:
4 - 2 1
- 4 2 1
- 4 - 2 1
The rows of D[2, 5, 1] in decimal are [3, - 1, - 5] and written as a matrix of binary digits, B[2, 5, 2] becomes: 0 2 1
0 0 - 1
- 4 0 - 1
The mappings above give the matrix D[2, 5, 2] of binary remainders which is:
- 4 2 1
4 2 - 1
- 4 2 - 1
Next, the decimal rows of D[2, 5, 2] are found by algebraic addition giving {- 1, 5, - 3] . This gives B[2, 5, 3] which is the matrix: 0 0 - 1 4 0 1 0 - 2 - 1
The zeros in B[2, 5, 3] are replaced as required by the above mappings to give D[2, 5, 3] which is: 4 2 - 1
4 - 2 1
4 - 2 - 1
Note that D[2, 5, 1] is dual to B[2, 5, 2] and D[2, 5, 2] is dual to B[2, 5, 3] and D[2, 5, 3] is dual to B[2, 5, 1]. In general D[N, Q[N, j], k] is dual to B[N, Q[N, j], [k + 1]] from k = 1 up to k = N and then next, D[N, Q[N, j], [N + 1]] is dual B[N, Q[N, j], 1]. We find that A[2, 5] is the matrix: 0 1 0
0 0 - 1
- 1 0 0
The matrix equations are found to be valid: A[2, 5].D[2, 5, 1] = D[2, 5, 2] and A[2, 5].D[2, 5, 2] = D[2, 5, 3] and A[2, 5].D[2, 5, 3] = D[3, 2, 1] indicating a cyclic quality. A was found by solving for the elements a[i, j] in the matrix equation: A[2, 5].D[2, 5, 1] = D[2, 5, 2].
The principal matrix of binary remainders: D[N, Q[N, j], [N + 1]] is dual to the primitive matrix of binary digits: B[N, Q[N, j], 1], and each is non-singular. These proofs are very straight-forward. .................................................................................... A slight digression.
Proof of the non-singularity of the principal matrix of binary digits: B[N, Q[N, j], 1] In the case of B[N, Q[N, j], 1], the elements below the principal diagonal are all zero and the elements on the principal diagonal are non-zero. The determinant: |B[N, Q[N, j], 1]| is found by multiplying out the elements on the principal diagonal. Since this product is non-zero, the corresponding matrix has an inverse and is therefore non-singular.
A typical principal matrix of binary digits is:
4 0 1
0 2 1
0 0 1
representing the uneven integer five [5] is self-evidently non-singular.
Proof that the principal matrix of binary remainders: D[N, Q[N, j], [N + 1]] is non-singular. The principal matrix of binary remainders that represents the integer five [5] is:
4 2 - 1
4 - 2 1
4 - 2 - 1
The procedure is to add minus one [ - 1] times the last row but one, to the last row.
The matrix becomes:
4 2 - 1
4 - 2 1
0 0 - 2
Next, add minus one [ - 1] times the last row but two, that is minus one times the first row, to the last row but one. The matrix becomes:
4 2 1
0 - 4 2
0 0 - 2
The first row is retained unaltered. Evidently, after these row operations, the determinant of D[2, 5, 3] representing five is unchanged and has non-zero entries on the principal diagonal and zero entries below the principal diagonal so that the determinant is non-zero and the corresponding matrix: D[2, 5, 3] is non-singular. Evidently the determinant: |D[2, 5, 3]| is equal to: 4 times - 4 times - 2, which is: thirty-two. The above proofs are easily generalized for the non-singularity of the principal matrices: B[N, Q[N, j], 1] and D[N, Q[N, j], [N + 1]].
End of digression.
The principal matrix D and its dual, the primitive matrix B, disregarding the transitional property, may be designated respectively: B[N, Q[N, j]] and D[N, Q[N, j]]
..........................................................................................
In the case of Q[2, 1], the determinant |A[2, 5]| is similar to the determinant of the identity matrix I[3], by interchanging rows or interchanging columns so that A[2, 5] is non-singular. It follows that D[2, 5, 1] D[2, 5, 2] and D[2, 5, 3] are all non-singular. The general structure of the [N + 1] by [N + 1] matrix A[N, Q[N, j]] probably consists of the permuted rows of the identity matrix I[N + 1] some elements of which become - 1 in place of + 1 and consequently the determinant of the matrix A[N, Q[N, j]], |A[N, Q[N, j]| would be expected to be + 1 or - 1. Non-singular matrices analogous to A that convert B[N, Q[N, j], k] into B[N, Q[N, j],[k + 1]] and B[N, Q[N, j],[N + 1]] into B[N, Q[N, j], 1] could be defined. [Compare the D[N, Q[N, j], k], with k taking successive values [1, ... [N + 1]] with Cyclic Groups.]
The purpose of having principal matrices of binary remainders that uniquely represent uneven integers, implicitly containing all the information about each such integer, is to decode the matrix and find the prime factors of the integer represented by the particular matrix directly using [no trial and error] linear algebra.
One process is to find the continued reverse product: D[N, Q[N, j], [N + 1]].D[N,[Q[N, j], N].D[N, Q[N, j], [N - 1]]. ... D[N, Q[N, j], 1] and then inspect the elements of the product matrix. The multiplication would proceed from right to left, starting with the matrix product: D[N, Q[N, j], 2].D[N, Q[N, j], 1] and then multiplying this by: D[N, Q[N, j], 3] and so on. This series of partial multiplications is calling out for a computer program.
Example: in the case of the matrix product: D[1, 3, 2].D[1, 3, 1] the multiplication is:
2 1 . 2 1 which is: 2 3 noting that Q[1, 1] = 3 occurs as an element. 2 - 1 - 2 1 6 1
SHAWWPG19410425 (talk) 14:56, 9 July 2012 (U.T.C)SHAWWPG19410425 (talk) 20:27, 17 January 2013 (U.T.C.)SHAWWPG19410425 (talk) 20:43, 17 January 2013 (UTC)SHAWWPG19410425 (discuss • contribs) 17:44, 2 May 2013 (UTC)