|
Computation trick for evaluation of ba power using a = a020 + a121 +a222 + ... an-12n-1 where ai = 0 or 1 is used to compute any shift register psuedorandom number in only the order of n operations starting with an initial vector. Can the values of ai be analyticially computed from knowledge of the initial vector and any shift register psuedorandom number? We will see. Lost in the super-universe theme song. But I've wandered much further today than I should And I can't seem to find my way back to the Wood But we got back two different ways. Pooh, too, can get back two ways. Directly, or back the other way around the world. We both practically and theoretically got back to where we started using the binary representation of the exponent computation trick. That means we can venture out into the super-universe, then algorithmically compute a matrix which can theoretically get us back. But can we practically invert that matrix? MAYBE! We are gaining more insight into inverting a matrix of any power of a companion matrix. By reducing the problem to a combination of 0s and 1s, sorting, ANDing, and mod 2 summing. |
|||||||||
Matrix C is the companion matrix.1 0 1 The inverse of C, C-1, is computed by forming the augmenting C by adding the identity matrix to the right then reducing C to the identity matrix using elementary row operations while performing the same operations on the identity matrix on the rightN1. 1 0 1 1 0 0 1 0 0 Thus 0 1 0 And that is C6. Test: 1 0 1 0 1 0 1 0 0 Commutative test 0 1 0 1 0 1 1 0 0 Six steps to compute the inverse can be replaced using the computation trick to compute C2x C4 = C6 since C23-1 = I
The above observation lead to the generality that the inverse of a power of a companion matrix is as easy to compute as any power using the exponent binary exponent computational trick as the power of the matrix. Let's look at the pseudorandom sequence produced by powers of the inverse companion matrix, C-1, for patterns while copying C-1 to the right to make multiply computation check easy 0 1 0 0 1 0 Assign first row binary weight 1, second row 2, third row 4 to get the number sequence 4, 2, 5, 6, 7, 3, 1. This is the reverse direction of the sequence formed by computing from powers of C: 3, 7, 6, 5, 2, 4, 1. Any pseudonoise column vector can be computed Ca where a = a020 + a121 +a222 + ... an-12n-1 times the initial column vector 1 c0 to some power even for superastronomical number a using the binary expansion of a computation trick. Can we analyticallyN1 find a = a020 + a121 +a222 + ... an-12n-1 where c0 1 Argument of why a matrix raised to the zeroth power is the identity matrix is given by WolframL3. Verification, other than the inverse, example is 0 1 0 1 1 1 1 0 0 1 1 0 goal is to compute a0, a1, and a2for any c0, c1, and c2 [not all zero] 1 1 0 22a2 + 2a1 + a0 1 c0 This is equivalent to 1 1 0 22a2 1 1 02a1 1 1 0 a0 1 c0Is a0 = 0 which means C = I or is a0 = 1 or C? a1 and a2 can be either zero or one so do we have to try all combinations? Or is there a shorter computation method? The initial column and target vector can be expressed as a power of either matrix C or C-1. A pattern emerges between columns. For example, a power of the companion matrix can be developed starting with the column vector of C3. ? indicates value unknown. 0 ? ?Multiplication of C5 by C-1 determines the ? values for C4 and C3. We can practically invert, even large matrices, using the binary exponent computational trick. Computation complexity of matrix inversionL7 is on the order of n3. But we've avoided this for 2i powers of companion matrices. The computation complexity is on the order of the number of bits in the exponent. Goal is to try to eliminate work to find the companion matrix inverse using the algorithm described in note N1. Conjecture is that the amount of work may be related to the power the companion matrix was raised. Elementary matrix operations can be used to interchange rows in a power of a companion matrix and associated identity augmentation. For example,
which means that the above two right matrices only need to be multiplied by 1 1 0 to get 1 0 0 1 0 1 which is the inverse of C6. Likewise C1 abd the identify matrixcan be multiplied by 1 0 1 0 1 0 0 0 1 to get 1 0 1 1 0 0 So sorting first using column 1 as the sort key, then zeroing 1 value entries in rows 2 and 3 by muliplication the appropriate elmentary matrix leads to an algorithm that efficiently reduces the power of a companion matrix to all zeros below the main diagonal which contains all ones. Implicit Matrix Multiplication Row exchanges, which can be used for sorting, and ANDing rows of a companion matrix and associated identity matrix is used instead of explicit matrix multiplies which are computationally operation-consuming. Common logarithms are defined to the base 10.
Thus
since
And
since
Logarithm of a binary companion matrixL2 is now defined as
Thus
since
And
since
|
|||||||||
|
|
|||||||||
| N1 Analytic solution is compared to searching.
Powers of C or C-1 can be computed to search for a solution. But
this doesn't work or large or super-astronomical numbers. |
|||||||||
|
|
|||||||||
| L1 Logarithm http://en.wikipedia.org/wiki/Logarithm L2 Logarithm of a matrix http://en.wikipedia.org/wiki/Logarithm_of_a_matrix L3 Matrix to the zero power. L4 Methods of matrix inversion http://en.wikipedia.org/wiki/Invertible_matrix L5 LU Decomposition http://mathworld.wolfram.com/LUDecomposition.html L6 Binary matrix (Java) http://en.literateprograms.org/Binary_matrix_(Java) L7 Computational complexity of mathematical operations http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations |
|||||||||
|
|
|||||||||
| N1 Denote the elementary pre-multiplication matrices
Ei. Then the product of all of the Eis times the matrix
to be inverted is the identity matrix. Correspondingly, the product times the
identity matrix is the inverse. |
|||||||||
|
|
|||||||||
|
