Explicit binary remainder matrices
From Wikiversity - Reading time: 5 min
Research Project: SQUARE NON-SINGULAR MATRICES CONTAINING BINARY REMAINDERS AS ELEMENTS ASSOCIATED WITH TWO RAISED TO THE APPROPRIATE BINARY PLACE VALUE. The Division Algorithm with divisor two [2] is usually written:
Q[n, N] = 2.Q[N - 1] + r{N - 1] Equation 1.
Q[n, N] is an uneven integer defined by Q[n, N] = 2.n + 1 where n = 1, 2, ... and Q[N] is identifiable with Q[N, n]. The quotient is an uneven integer, provided that the remainder is given by: r[N - 1] = [i]**{1 + Q[n, N]} The inequalities: 2**{N} < Q[n, N] < 2**{N + 1} are required to be satisfied by Q[n, N], thereby setting a lower and upper limit on [n]. The least value of Q[n, N] is [2**{N} + 1], for example, from which n[minimum] can be found. The greatest value of Q[N, n] is [2^{N + 1} - 1] from which n[maximum] can be found. [noting that the symbols: ** and: ^ both mean the same thing, exponentiation] In the context, Q[N] can be identified with Q[n, N] If Equation 1. is rearranged to:
Q[N - 1] = 1/2[Q[n, N] - [i]**{1 + Q[n, N]}] Equation 2.
and iterated: Q[N - 2] = 1/2[Q[N - 1] - [i]**{1 + Q[N - 1]}]
..............................................
Q[1] = 2.Q[0] + r[0] This is the final equation.
that is needed to produce square matrices. There are [N + 1] uneven integers from the iteration above: Q[n, N], Q[N - 1], Q[N - 2], .... Q[1], Q[0] and if these are set explicitly in binary, then they fall naturally into a square non-singular matrix. In explicit binary:
Q[n, N] = b[N].2**{N} + b[N - 1].2**{N - 1] + ..2**{k}.b[k] .. + b[0]
Q[N - 1] = 0 b[N].2**{N - 1} + b[N - 1].2**{N - 2} + b[0]
................................................................................
Q[0] = 0 0 0 + b[0]
Calling the matrix of binary digits B[n, N, [N + 1]], set the elements: b[1, 1] = 2**{N}, b[1, 2] = b[N - 1].2**{N - 1} ... b[1, N], b[1, N] = b[1].2**{1}, [N + 1]] = b[0] b[2, 1] = 0, b[2, 2] = b[N].2**{N - 1}, ... b[2, N] = b[2].2**{1}, b[2, [N + 1]] = b[0] the pattern continues to give the final row: b[[N + 1], 1] = 0, ...b[[N + 1], 2] = 0, b[[N + 1], N] = 0
b[[N + 1], [N + 1]] = b[0].
EXAMPLE: Q[12, 4] = 53 , n = 26, N = 5, and in explicit binary is: 32 + 16 + 0 + 4 + 0 + 1 The matrix of binary digits is:
B[26, 5, 6] is: 32 16 0 4 0 1
0 16 8 0 2 1
0 0 8 4 0 1
0 0 0 4 2 1
0 0 0 0 2 1
0 0 0 0 0 1
Since Q[n, N] is uneven, b[0] = 1 and b[N] = 1 is the most significant digit.
Substituting: r[N - k] = 2.b[k] - 1 into the expression
for Q[n, N] gives Q[n, N] in terms of its remainders. The remainders r[N] = 1 and r[0] = 1, because of the
corresponding values of b[0]and b[N]. The binary digit b[0] = 1, the least significant digit, because Q[N] is uneven and b[N] = 1 and is the most significant binary digit.
Q[n, N] = 2**{N} + 2**{N - 1} + r[1].2**{N - 2} + r[2].2**{N - 3} + ... + r[N - 1]
In the above example, r[1], r[2], r[3], and r[4] are required.
r[4] = [i]**{1 + Q[27, 5]}, r[3] = [i]**{1 + Q[4]}, r[2] = [1]**{1 + Q[3]}, r[1] = 3.
Subtituting these values into Q[27, 5] = 53 in the above equation in terms of remainders produces the first row of D[n, N, N + 1], the dual matrix of remainders, having [N + 1] rows and [N + 1] columns. There are no elements of value zero in this matrix of remainders. The remaining elements can be inferred from the pattern of simple examples.
In the above example: D[26, 5, 6] is:
32 16 8 - 4 2 - 1
32 - 16 8 4 - 2 1
32 - 16 - 8 4 2 - 1
32 - 16 - 8 - 4 2 1
32 - 16 - 8 - 4 - 2 1
32 - 16 - 8 - 4 - 2 - 1
The algebraic sums of the rows of D[26, 5, 6] are found to correspond to
Q[27, 5], Q[4], Q[3], Q[2], Q[1], Q[0].
There are general expressions for the elements of D[n, N, [N + 1]], that is dual to B[n, N]. Each matrix D has been found to be non-singular in simple actual instances and is non-singular in all cases, as can be easily proved. Each uneven integer Q[n, N] is uniquely represented by a matrix B[n, N] and its dual matrix D[n, N, [N + 1]]. The subscript: [N + 1] that is the order of a square matrix can be discarded, since the order is always: [N + 1] PROOF OF NON-SINGULARITY OF D[N, n]. In the example above, D[5, 26] that represents Q[5, 26] which is the integer 53, D[5, 26] is seen to be non-singular by the following process on the determinant: |D[5, 26]|: Row 1 of the determinant of D is left unaltered and written down. Row 1 is multiplied by - 1 and added to row 2 of the original determinant and this new row 2 is written down. The original row 2 is multiplied by - 1 and added to row 3 of the original determinant so producing the new row 3 which ia again written down. This is continued until the original row 4, multiplied by - 1 is added to the final row which is row 6. The new determinant is:
|D[5,26]| := 32 16 8 - 4 2 - 1
0 - 32 0 8 - 4 2
0 0 - 16 0 4 - 2
0 0 0 - 8 0 2
0 0 0 0 - 4 0
0 0 0 0 0 - 2
This determinant has evidently a non-zero value and therefore the corresponding original matrix: D[5, 26] is non-singular.
THE GENERAL CASE: D[N, n] The elements of D[N, n] are given by the consecutive terms of the consecutive equations that represent in sequence: Q[N, n], Q[N - 1], ... Q[0] in terms of the binary remainders: r[N], r[N - 1], ... r[1], r[0]. As stated above, r[0] = 1 and r[N] = 1. The remainders: r[N - 1], ... r[1] have values of either + 1 or - 1 with 2^{N - 1} variations. The equations are:
Q[N] = 2^{N} + 2^{N - 1} + r[1].2^{N - 2} + r[2].2^{N - 3} + ... + r[N - 1]
Q[N - 1] = 2^{N} - 2^{N - 1} + 2^{N - 2} + r[1].2^{N - 3} + r[2].2^{N - 4} + ... + r[N - 2] .....
Q[0] = 2^{N} - 2^{N - 1} - 2^{N - 2} ... - - 1
There [N + 1] equations, above, having each [N + 1] terms, producing the [N + 1] row and [N + 1] column matrix: D[N, n]. The addition of the negative of an above row to particular row gives a determinant having non-zero elements on the principal diagonal and a triangle of zeros below the principal diagonal. THE SIMPLIFIED EIGENVALUE DETERMINANT: |D[N, n, x]| The primitive starting eigenvalue determinant is processed as above in the proof of non-singularity to give a much simpler form. Two examples may serve to indicate the structure of the simplified determinant of D. Example [i] For Q[1, 1]] = 3, |D[1, 1, x]| is: |[2 - x] 1 |
| 2 [- 1 - x]|
The above is the form of the primitive determinant in [x] of the matrix D[1, 1] Leaving row 1 unchanged but adding - 1 times row 1 to row 2 gives the simplified determinant [but not really simpler in the case of Q[1, 1] = 3], but simpler for all successive instances.
|D[1, 1, x]| becomes: |[2 - x] 1 |
| x [- 2 - x]|
Example [ii] For Q[4, 15] = 31, row 1 is left unaltered but every successive row down to the last but one is multiplied by - 1 and added to the row below that row.
The primitive |D[4, 15, x]| is: [16 - x] 8 4 2 1
16 [- 8 - x] 4 2 1
16 - 8 [- 4 - x] 2 1
16 - 8 - 4 [- 2 - x] 1
16 - 8 - 4 - 2 [- 1 - x]
Using the process to prove non-singularity to the primitive determinant above gives the simpler determinant:
[16 - x] 8 4 2 1
x [- 16 - x] 0 0 0
0 x [- 8 - x] 0 0
0 0 x [- 4 - x] 0
0 0 0 x [- 2 - x]
The elements of the simplified determinant below the non-principal diagonal comprising x's are all zeros for every case where Q > 3 and in general the elements above the principal diagonal but below the first row are not necessarily zero.
The matter of interest in the first instance here is to compute the amplitudes and arguments of the eigenvalues and analyse the results for Q = [1], 3, 5, 7, 9, ... so as to gain an insight into prime numbers and the prime factors of non-prime uneven integers.
2.99.204.18 22:38, 31 January 2011 (UTC)SHAWWPG19410425 (talk) 18:27, 16 June 2012 (UTC)
EncycloReader
is supported by the 
KSF