Matrices of binary remainders
Research Project: The object is: [a] to be able to distinguish a prime by what it is rather than by what it is not, using purely linear algebraic processes. [b] to be able to factorize a composite into its prime factors not by any trial and error procedure, but directly using linear algebra. This latter object [b] looks to be a very interesting practical problem.
This consists of plotting the amplitudes and arguments of the carefully labeled eigenvalues [zeros] and their corresponding characteristic vectors for each successive MATRIX OF BINARY REMAINDERS so providing an unsophisticated way of accessing the Prime Sequence and the complementary Composite Sequence of Uneven Non-primes. By that is understood: [3, 5, 7, 11, ... ] being the prime sequence and [1, 9, 15, 21, 25, 27, 33, 35, 39 ... ] being the composite sequence of non-prime uneven integers. Even integers cannot be represented as a matrices of binary remainders.
Composites of the form: 2^{K}.C, where C comes from the sequence of uneven composites above and K is an integer: [1, 2, ... ] are of no interest in the present context.
The zeros of the eigenvalue equations [and the characteristic vectors and their norms] of the Matrices of Binary Remainders that represent prime numbers are expected to provide an immediate insight into the sequences of the prime and composite numbers.
Each matrix of binary remainders implicitly contains all the information about the interior structure of the uneven integer, prime or composite, that it represents. The coefficients of the descending powers of two, reading from left to right, are either minus unity or plus unity and are the binary remainders found as described below.
There are some immediate results: given that a composite lies between 2^{N} and 2^{N + 1} then the largest prime factor of [2^{N + 1} - 1], given that this uneven number is a composite, then the least composite or prime in this range that is [2^{N} + 1], cannot be a factor of the greatest uneven integer, [2^{N + 1} - 1]. For example, we have proved that thirty-three cannot be a divisor of sixty-three.
From this it follows that the prime factors of any composite between 2^{N} and 2^{N + 1} are less than 2^{N} + 1. These ideas are easily proved.
Proof: try dividing [2^{N + 1} - 1] by two [2]. The quotient is: 2^{N} - 1/2. Now if a number is divided in succession by [a], then by [b] where [b] is greater than [a], then the quotient upon division by [b] is lesser than the quotient upon division by [a]. The least prime factor of a composite: [2^{N + 1} - 1], for some value of N, is three [3]. Division by two gives a quotient of [2^{N} - 1/2], so division by three [3] gives a quotient of less than [2^{N} - 1/2]. Now, division of a composite by a prime factor of at least three [3] gives a quotient that is another uneven integer and this uneven integer has, in view of the above, to be less than [2^{N} + 1] . Consequently, the matrices representing the prime factors of any composite: C, such that: 2^{N} < C < 2^{N + 1} are singular and have fewer than [N + 1] characteristic vectors. This follows from the construction of M.B.R.'s that have at least two identical rows in the matrices that represent the prime factors of the composite C.
From the above results, it follows from the construction of Matrices of Binary Remainders that the M.B.R.'s that represent the prime factors of any composite in the range 2^{N} to 2^{N + 1} are singular and that their characteristic equations have fewer than [N + 1] roots [zeros], apart from some repeated values of zero.
From the above, characteristic vectors of the M.B.R.'s of the prime factors span a subspace of the space of dimension [N + 1}, spanned by the composite, [C] itself, where the composite satisfies the inequalities in the range: 2^{N} < C < 2^{N + 1}.
The matrices: H, square of order [N + 1] defined below, only exist for primes and composites in the above range, and not for the matrices of this order that represent the prime factors. This is because M.B.R's of order [N + 1] by [N + 1] that represent integers that are less than 2^{N} are singular, having at least two identical rows that always include the last row.
There is an isomorphism of the intersection of two vector spaces to the null space of the matrix produced by adjoining the columns of the two sets of vectors constituting the two intersecting vector spaces. This is a very useful theorem.
The truth of this statement which is indicated for the present context, but is quite general, is as follows:
A vector in a space may be defined in terms of a linear combination of basis vectors. Given:
[α[1], ... α[K + 1]] is a basis for one vector space and [β[K + 2], ... β[K + N + 3] for another vector space, where the column vectors: α[1], ... β[K + N + 3] have [N + 1] components.
Then, if we can write: x[1].α[1] + ... + x[K + 1].α[K + 1] = x[K + 2].β[K + 2] + ... + x[K + N + 3].β[K + N + 3]
, then the left side and the right side of this equation each represent the same vector that is in the intersection of the spaces spanned by each set of basis vectors. The right side of the above equation is now transposed to the left, giving:
x[1].α[1] + .... x[K + 1].α[K + 1] - x[K + 2].β[K + 2] - ... - x[K + N + 3]β[K + N + 3] = [0]
and the symbol: [0] means the column vector having [N + 1] components, each of value zero.
It follows that the column vector [written as a row]
- [x[1], ... x[K + 1], - x[K + 2], ... - [K + N + 3]] is in the null space of the matrix produced by adjoining the two sets of column vectors that constitute the two basis sets of the two intersecting vector spaces.
To find the basis of the space of intersection, all that is needed is to find the unknowns: [x[1], ... x[K + 1]] and the unknowns: [x[K + 2], ... x[K + N + 3]]from the adjoined matrix and multiply out the linear combinations of the respective basis sets by the respective set of unknowns that have been found by solving the homogeneous equation. This isomorphism theorem is perfectly general to linear algebra.
The purpose of taking [K + 1] vectors in the first basis and [N + 1] vectors in the second basis is to have the inequality: K < N and have a composite, C satisfying the inequality: 2^{N} < C < 2^{N + 1}. Then if a prime factor, P of C satisfies the inequality: 2^{K} < P < 2^{K + 1}, the prime factor can be represented as a [K + 1] by [K + 1] non-singular matrix of binary remainders, but more pertinently can be represented as an: [N + 1] by [N + 1] singular [B.R.E.] matrix having fewer than [N + 1] proper characteristic vectors, just [K + 1]. This means that the vector space spanned by the [K + 1] characteristic vectors of the B.R.E. representing the prime factor, P is a proper subspace of the [N + 1] characteristic vectors spanning the [N + 1] dimension space, of the B.R.E. representing the composite, C.
In the study of these abstract vector spaces, the prime factors of a composite might just come out in the wash.
Certainly much more could be learned about the prime sequence since each prime number is represented now by a set of characteristic vectors in a hyperspace. There are in fact an infinite number of sets of characteristic vectors that represent the prime sequence, depending on the order: [N + 1] of the largest matrix used to represent the prime sequence up to the largest prime, set by the order of this matrix. For example: the primes: 7919 and 7927 satisfy the inequality:
2^{12} < 7919, 7927, < 2^{13}
so that every prime from three up to to last prime in the above interval could be represented by sets of characteristic column vectors each having thirteen components.
The simplest examples are for the composites: Q = 9, having two identical prime factors and Q = 15, the least composite to have distinct prime factors.
For example, the least composite having distinct prime factors, fifteen [15] is represented by the matrix:
8 4 2 1
8 - 4 2 1
8 - 4 - 2 1
8 - 4 - 2 - 1
This is the smallest matrix that can represent the number fifteen.
The number three [3] is representable by the matrix:
8 - 4 - 2 1
8 - 4 - 2 - 1
8 - 4 - 2 - 1
8 - 4 - 2 - 1
The number five [5] is representable by the matrix:
8 - 4 2 - 1
8 - 4 - 2 1
8 - 4 - 2 - 1
8 - 4 - 2 - 1
The above matrices representing the prime factors three and five are of larger order than the minimum required to represent these numbers. This is so that a proper comparison can be made with the matrix representing the number fifteen. An inspection of the eigenvalues and characteristic vectors of the matrices of the same order [four by four] as above, that represent the numbers three and five and comparison with the eigenvalues and characteristic vectors of the above matrix representing fifteen may reveal the factorization of the number fifteen. If this proves to be the case, then in principle any composite of any finite magnitude could be resolved into its prime factors purely by the processes of linear algebra. A question arises as to whether the characteristic vectors are orthogonal or not. If not, then the characteristic vectors can be made orthogonal by the Gram-Schmidt algorithm.
An outline of the process to find these matrices is as follows:
An example of such a matrix is: D[4, 11] uniquely representing the number 21.
Writing the row: [21, 11, 5, 3, 1] as a column in explicit binary, the matrix of binary digits B[4, 11] is
16 0 4 0 1
0 8 0 2 1
0 0 4 0 1
0 0 0 2 1
0 0 0 0 1
Noting the diagonal pattern.
The corresponding matrix of binary remainders D[4, 11] is:
16 8 - 4 2 - 1 16 - 8 4 - 2 1 16 - 8 - 4 2 - 1 16 - 8 - 4 - 2 1 16 - 8 - 4 - 2 - 1
Again, noting the diagonal pattern. The sums of the elements of the corresponding rows of the matrices above, are the same.
The assertion is that any uneven integer can be uniquely represented by a non-singular matrix of binary digits: B[N, n] having [N + 1] rows and [N + 1] columns and a non-singular dual matrix D[N, n] having [N + 1] rows and [N + 1] columns, the latter containing no elements of value zero, as in the latter matrix in the above example. The uneven integer: Q[N, n] = [2.n - 1], n = 1, 2, ... where Q[N, n] satisfies the inequalities: 2**{N} < Q[N, n] < 2**{N + 1} is such a number.
The lower limit on [n] is given by 2.n[minimum] - 1 = 2**{N} + 1 and the upper limit on [n] is given by 2.n[maximum] - 1 = 2**{N + 1} - 1, to be consistent with the inequalities above. [It is better to define an uneven integer as: Q[N, n] = [2.n - 1] because then the integer: [n] is the ordinal in which the integer: Q[N, n] occurs rather than setting: Q[N, n] = [2.n + 1] The the lower and upper limits of the integer [n] in the above inequalities are different when the expression: [2.n + 1 is used. Subsequent to Q[N, n], the remaining rows of the above matrices are given by iteration of:
Q[N - 1] = 1/2[Q[n, N] - [i]**{1 + Q[n, N]}]
Imaginary [i] satisfies: [i]**{2} = - 1.
counting down to:
Q[0] = 1/2[Q[1] - [i]**{1 + Q[1]}],
Invariably, Q[1] = 3 and Q[0] = 1.
The general remainder: r[j - 1] = [i]**{1 + Q[j]} Q[N] is identifiable with Q[N, n].
Each row is in explicit binary [having the powers of two in place]. The general matrix of binary digits B[N, n] is easily found from the pattern produced by iteration. The general matrix of binary remainders derived below, can easily be found by writing Q[N, n] = 2**{N} + b[N - 1].2**{N - 1} + ... + b[k].2**{k} + ... + b[0] The terms on the right of the above equation gives the elements of the first row of the matrix: B[N, n]. Thus b[1, 1] = 2**{N}, b[1, 2] = b[N - 1].2**{N - 1}, ... b[1, N] = b[1].2**{1}, b[1, [N + 1]] = 1. By inspection of an example, Q[N - 1] = 2**{N - 1] + b[N - 1].2**{N - 2} + ... + b[2].2**{1} + 1 The elements of the second row of B[N, n] are: b[2, 1] = 0, b[2, 2] = 2**{N - 1}, b[2, 3] = b[N - 1].2**{N - 2}, b[2, N] = b[2].2**{1}, b[2, [N + 1]] = 1 The pattern is seen by inspection of a simple example of a binary digit matrix as B[4, 11] above, looking at lines of elements parallel to the principal diagonal. Finally since Q[0] = 1, the elements of the last row of B[n, N] are: b[[N + 1], 1] = 0, ... b[N + 1], N]] = 0, b[[N + 1], [N + 1]] = 1. The binary coefficient: b[N] = 1, the most significant digit and b[0] = 1 since Q[N, n] is uneven. Using the formula connecting the binary digits to the binary remainders:
b[k] = [1/2].[r[N - k] + 1]
and substituting for b[k] into the above expression for Q[N, n] gives Q[N, n] in terms of its remainders. Each term of this new equation becomes an element of the first row of D[N, n]. Note that r[N] = 1 corresponding to b[0] = 1 and r[0] = 1 corresponding to b[N] = 1. The remaining rows of D[N, n] are found from the pattern indicated by elements in lines parallel to the principal diagonal elements taken from a simple case for example. Only the remainders: r[1], ... r[N - 1] vary in the interval: 2**{N} to 2**{N + 1}. Q[N, n] in terms of its remainders is:
Q[N, n] = 2**{N} + 2**{N - 1} + r[1].2**{N - 2} + ... + r[N - 1]
Q[N - 1] in terms of its remainders is:
Q[N - 1] = 2**{N} - 2**{N - 1} + 2**{N - 2} + r[1].2**{N - 3} + ... + r[N - 2]
The two above equations establish the pattern for the matrix D[N, n]
and the last row of D[N, n] is given by:
Q[0] = 2**{N} - 2**{N - 1} - 2**{N - 2} - ... - 1
The elements d[i, j] of D[n, N] are: d[1, 1] = 2**{N}, d[1, 2] = 2**{N - 1}, d[1, 3] = r[1].2**{N - 3}, ... d[1, [N + 1]] = r[N - 1] d[2, 1] = 2**{N}, d[2, 2] = - 2**{N - 1}, d[2, 3] = 2**{N - 2}, d[2, 4] = r[1].2**{N - 3}, ... d[2, [N + 1]] = r[N - 2] and following the pattern, d[[N + 1], 1] = 2**{N}, d[[N + 1], 2] = - 2**{N - 1}, ... d[[N + 1], [N + 1]] = - 1
Evidently, the rules of linear algebra are applicable to the matrices B[N, n] and to its dual D[N, n]. [Dual in the sense that the algebraic sum of a row of D is the same as the algebraic sum of the corresponding row of B.]
The non-singularity of the matrix B[N, n] is self-evident since B[N, n] has zero elements below the principal diagonal, exclusively and non-zero elements on the principal diagonal. Consequently, the determinant: |B[N, n]| is non-zero and therefore equivalently, the matrix B[N, n] is non-singular.
The proof that the matrix D[N, n] is non-singular is very straight forward. First taking the above matrix D[4, 11] as an example: Row [1] of |D| is row [1] of the transformed determinant |D|. That is row [1] is unchanged in the determinant: |D[4, 11]|. Next, Row [4], the last but one row of the matrix D has its elements multiplied by - 1 and these are added to the elements of the fifth and last row, row [5] so giving the following transformed row [5] of the determinant |D|:
0 0 0 0 - 2
Next, the elements of row [3] of the matrix D are multiplied by - 1 and these are added to the corresponding elements of row [4] of the [original] matrix D. This gives the transformed row [4] of the determinant: |D|:
0 0 0 - 4 2
Next, the elements of row [2] are multiplied by - 1 and added to the corresponding elements of row [3] [of the original] matrix |D|. This gives the transformed row [3] of the determinant |D|:
0 0 - 8 4 - 2
Finally in this example, the elements of row [1] of the matrix D are multiplied by - 1 and are added to the corresponding elements of row [2] [of the original] matrix D. These become the elements of the transformed row [2] of the determinant |D|:
0 - 16 8 - 4 2
And the first of the matrix D was unchanged giving the first row of the determinant |D|.
Writing out the rows of the determinant |D| in the proper order, we have:
16 8 - 4 2 - 1
0 - 16 8 - 4 2
0 0 - 8 4 - 2
0 0 0 - 4 2
0 0 0 0 - 2
The transformed determinant |D| is evidently non-zero by the same argument that applied to the determinant of the matrix |B| and consequently the matrix: D[4, 11] is non-singular.
General proof of the non-singularity of the matrix of binary remainders: D[N, n] The very same process as for D[4, 11] applied to the general matrix D[N, n] leaves the first row of the transformed determinant |D[N, n]| unchanged as before. Row [N] of the matrix elements of D[N, n] is multiplied by - 1 and added to the last row, row [N + 1] of the corresponding elements of D[N, n] giving the last row, row [N + 1] of the transformed determinant |D[N, n]| which is:
0 0 0 ... 0 ... - 2,
there being N zero elements followed by the element [N + 1, N + 1] in the last row and last column of |D|. Next, row [N - 1] is multiplied by - 1 and added to row [N] of [the original] matrix D[N, n]. This process is continued until row [1], multiplied by - 1 is added to row [2] [of the original] matrix D. We are left with a determinant |D[N, n]| where the [N + 1] entries on the principal diagonal are non-zero and every entry below the principal diagonal is zero. The determinant |D| is non-zero in value and therefore the matrix D[N, n] is non-singular.
The process of proving the non-singularity of D[N, n] leads to a much simplified form of the determinant: |D[N, n, x| of the eigenvalue matrix equation: D.X = λ.X facilitating the derivation of the characteristic equation. Example [1] The first non-degenerate eigenvalue determinant is for Q[1, 2] = 3 This is:
|D[1, 2, x]| = |[2 - x] 1 |
| 2 [- 1 - x] |
Adding minus one times row one to row two gives:
|D[1, 2, x]| = | [2 - x] 1 |
| x [- 2 - x]|
Example [2] Q[4, 16] = 31 The process of adding the negative of the row above a particular row to that row is repeated as above in Example [1]. The primitive form of the determinant of: D[4, 16] is:
|D[4, 16, x]]| = |[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]|
The determinant: |D[4, 16, x]| becomes: |[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 procedure for finding the simplest form of the determinant characteristic equation as in Example [2] above from the primitive form of the matrix: D[N, n, x] can be reversed by starting from unaltered row 1 and finally adding the negative of row [N} to row [N + 1]. Setting x = 0 in the simplest form of the determinant evidently proves the non-singularity of the matrix: D[4, 16] and likewise in the general case of the matrix: D[N, n]. ........
A matrix H can be defined that transforms B into D, thus:
H.B = D
This implies that H = D.[B**{ - 1}] and B = H**{ - 1}.D and H**{ - 1} = B.D**{ - 1}.
An example of the matrix H is H[4, 16] representing Q[4, 16] = 31 This matrix is:
1 0 0 0 0
1 - 2 2 0 0
1 - 2 0 2 0
1 - 2 0 0 2
1 - 2 0 0 0
having three zeros on the principal diagonal, yet non-singular. This required first finding [B[4, 16]]**{ - 1}], found by solving twenty-five very simple equations for the elements of the inverse matrix and finding D[4, 16]. The matrices of transition, H of the examples worked out, have one real eigenvalue unity [1] and the remaining complex eigenvalues lie on a circle, center the origin and radius two units. Presently, there are no results for the eigenvalues of H**{ - 1} for any instances.
The research consists in finding and plotting the eigenvalues labelled according to the Q[N, n] to which they relate and finding the norms of the corresponding characteristic vectors of the matrix of binary digits B[N, n] and the matrix of binary remainders D[N, n] and other related matrices such as: B.D.B**{ - 1}, D.B.D**{ - 1}, H and H**{ - 1} etc. and interpreting the results. The amplitudes [moduli] of the complex eigenvalues and their multiplicities if such exist of the above matrices may have significance in the present context. Much insight can be gained by working on matrices of the least orders. such as: B[1, 2], D[1, 2] representing Q[[1, 2] = 3
That is B[1, 2] is 2 1 and D[1, 2] is 2 1
0 1 2 - 1
The eigenvalue equation for D[1, 2] is: x**{2} - x - 4 = 0 The zeros of D[N, n] may be generally designated as: x[N, n, 1], ... x[N, n, [N + 1]] since the eigenvalue equation of D[N, n] is of degree: [N + 1]. In the case of D[1, 2], x[1, 2, 1] = 2.561552813 and x[1, 2, 2] = - 1.561552813
The matrix B[2, 3] is 4 0 1 and D[2, 3] is 4 2 - 1
0 2 1 4 - 2 1
0 0 1 4 - 2 - 1
The eigenvalue equation for D[2, 3] is: x**{3} - x**{2} - 12.x - 32 = 0 The eigenvalues for D[2, 3] are: x[3, 2, 1] = 4.842584649
x[3, 2, 2] = - 1.921292324 + 1.707828222.i
x[3, 2, 3] = - 1.921292324 - 1.707828222.i
The matrix B[2, 4] is 4 2 1 and D[2, 4] is 4 2 1
0 2 1 4 - 2 1
0 0 1 4 - 2 - 1
The eigenvalue equation for D[2, 4] is: x**{3} - x**{2} - 20.x - 32 = 0 The eigenvalues for D[2, 4] are: x[4, 2, 1] = 5.595924581
x[4, 2, 2] = - 2.29796229 + 0.6616771461.i
x[4, 2, 3] = - 2.29796229 - 0.6616771461.i
The eigenvalues of B[N, n] are mathematically trivial but not necessarily, the norms of the corresponding characteristic vectors. The Dual Matrices of Binary Remainders have been found in every instance to be non-singular as proved above, that is the matrices are invertible and the reciprocal matrices can be found.
The non-singularity of B[N, n] was self evident. The research consists in finding and plotting the labelled [Am. labeled] eigenvalues particularly and the characteristic vectors, principally of the the Dual Matrices of Binary Remainders and relating these to the uneven integers that are represented by the matrices. The cases of N = 2 and at most N = 4 can be worked out on paper, just about. Realistically, for the case of N = 5 and beyond, computer programs are needed to expedite the research.SHAWWPG19410425 (talk) 18:48, 8 June 2012 (U.T.C.)SHAWWPG19410425 (talk) 21:59, 1 June 2012 (U.T.C.)SHAWWPG19410425 (talk) 21:51, 20 December 2012 (U.T.C.)
SHAWWPG19410425 00:51, 3 February 2011 (U.T.C.)SHAWWPG19410425 01:11, 3 February 2011 (U.T.C.)SHAWWPG19410425 13:31, 3 February 2011 (UTC)SHAWWPG19410425 17:22, 5 February 2011 (UTC)SHAWWPG19410425 19:31, 5 February 2011 (UTC)SHAWWPG19410425 12:57, 6 February 2011 (UTC)SHAWWPG19410425 11:59, 7 February 2011 (UTC)SHAWWPG19410425 12:04, 7 February 2011 (UTC)SHAWWPG19410425 10:06, 3 March 2011 (UTC)SHAWWPG19410425 12:38, 19 March 2011 (UTC)SHAWWPG19410425 21:43, 27 March 2011 (UTC)SHAWWPG19410425 14:47, 31 March 2011 (UTC)SHAWWPG19410425 18:50, 31 March 2011 (UTC)SHAWWPG19410425 11:47, 5 April 2011 (UTC)SHAWWPG19410425 (talk) 19:01, 20 December 2012 (U.T.C.)SHAWWPG19410425 (talk) 21:51, 20 December 2012 (U.T.C.)SHAWWPG19410425 (talk) 12:33, 9 January 2013 (U.T.C.) β