Re: fast matrix determinant

From	hum9 <obi65537@gmail.com>
Newsgroups	comp.lang.forth
Subject	Re: fast matrix determinant
Date	2017-06-16 10:21 +0300
Organization	A noiseless patient Spider
Message-ID	<oi00ml$lab$1@dont-email.me> (permalink)
References	(4 earlier) <ohrj4a$jra$1@dont-email.me> <ohtb25$t0m$1@dont-email.me> <ef709c75-138b-4e9c-ad5b-08d40b24914f@googlegroups.com> <ohu72p$nob$1@dont-email.me> <1435c2f6-0633-4ed3-9dd1-e68d30442114@googlegroups.com>

Show all headers | View raw

On 16.06.2017 05:06, krishna.myneni@ccreweb.org wrote:
> On Thursday, June 15, 2017 at 9:57:56 AM UTC-5, hum9 wrote:
>> On 15.06.2017 13:30, krishna...org wrote:
> ...
>>>
>>> That's a clearer statement, but a definition of "small" is needed. Let's try a numerical experiment, using R, below. The results seem to show that your theorem doesn't work very well, when the perturbations are at the 1e-3 level.
>>>
> ...
>>> ## Make a square matrix, [A]
>>>> A <- matrix(c(12, -51, 4, 6, 167, -68, -4, 24, -41),
>>>     nrow = 3, byrow = TRUE)
>>>> A
>>>        [,1] [,2] [,3]
>>> [1,]   12  -51    4
>>> [2,]    6  167  -68
>>> [3,]   -4   24  -41
>>>
>>>
>>> ## Obtain the eigenvectors of A as the matrix C.
>>>> C <- eigen(A)$vectors
>>>> C
>>>              [,1]      [,2]       [,3]
>>> [1,]  0.3281474 0.2547577 -0.9905263
>>> [2,] -0.9368814 0.3027934  0.0871754
>>> [3,] -0.1207170 0.9183761  0.1061044
>>>>
> ...
>>>
>>> ## The perturbed matrix, A' = A + dA
>>>
>>>> A_prime <- A + dA
>>>> A_prime
>>>             [,1]      [,2]       [,3]
>>> [1,] 12.000310 -50.99927   4.000287
>>> [2,]  6.000988 167.00072 -67.999136
>>> [3,] -3.999051  24.00051 -40.999968
>>>
>>> ## Compute eigenvalues for A and A_prime
>>>
>>>> L <- eigen(A)$values
>>>> L_prime <- eigen(A_prime)$values
>>>
>>> ## Compute change in eigenvalues using hum9's theorem:
>>>> B <- CT %*% dA %*% C
>>>> B
>>>                 [,1]          [,2]          [,3]
>>> [1,]  0.0002396215 -0.0010482326  8.106709e-04
>>> [2,] -0.0004493261  0.0009161406 -1.123436e-03
>>> [3,]  0.0005559052 -0.0004037818  4.391405e-05
>>>
>>> ## Compare diagonal elements of above matrix
>>> ## with actual change in eigenvalues
>>>> L_prime - L
>>> [1] 0.0004830448 0.0003955184 0.0001790197
>>>>
>>
>> [C]^T * [C] should be [I], but is:
>>
>> 1.00000006788172 -0.31094703528148 -0.41952024562898
>> -0.31094703528148 0.99999998984406 -0.12850432115031
>> -0.41952024562898 -0.12850432115031 1.00000004505621
>>
>> Looks that eigenvectors are not orthonormal.
>> ...
> 
> Yes, you're quite correct. In order to ensure the eigenvectors are orthogonal, we must start with a real symmetric matrix. Let's check the theorem in the case of a real symmetric matrix:
> 
>> A <- matrix(c(12, -51, 4, -51, 167, -68, 4, -68, -41),
> + nrow=3, byrow=TRUE)
>> A
>       [,1] [,2] [,3]
> [1,]   12  -51    4
> [2,]  -51  167  -68
> [3,]    4  -68  -41
> 
> ## The eigenvectors of A; each column
> ## is a separate eigenvector.
>> C = eigen(A)$vectors
>> C
>             [,1]       [,2]      [,3]
> [1,]  0.2569501  0.9526354 0.1626730
> [2,] -0.9291492  0.1972167 0.3127096
> [3,]  0.2658164 -0.2314982 0.9358153
> 
> ## Transpose of eigenvector matrix:
>> CT = t(C)
>> CT
>            [,1]       [,2]       [,3]
> [1,] 0.2569501 -0.9291492  0.2658164
> [2,] 0.9526354  0.1972167 -0.2314982
> [3,] 0.1626730  0.3127096  0.9358153
> 
> ## Check orthogonality of eigenvectors
> ## of A. Zeroing elements which have
> ## abs value < 1e-15 will leave us with
> ## the identity matrix, below. Yes, we
> ## have orthogonal eigenvectors!
>> CT %*% C
>               [,1]         [,2]         [,3]
> [1,] 1.000000e+00 1.595946e-16 1.665335e-16
> [2,] 1.595946e-16 1.000000e+00 1.110223e-16
> [3,] 1.665335e-16 1.110223e-16 1.000000e+00
>>
> 
> ## Create a perturbation matrix, dA:
>> p <- runif(length(A))/1000
>> dA <- matrix(p, nrow=3, byrow=TRUE)
>> dA
>               [,1]         [,2]         [,3]
> [1,] 0.0002611730 0.0001076001 0.0004993786
> [2,] 0.0002825590 0.0004750525 0.0003822412
> [3,] 0.0008472763 0.0005271824 0.0007238125
> 
> ## The perturbed matrix, A' = A + dA:
>> A_prime <- A + dA
>> A_prime
>             [,1]      [,2]       [,3]
> [1,]  12.000261 -50.99989   4.000499
> [2,] -50.999717 167.00048 -67.999618
> [3,]   4.000847 -67.99947 -40.999276
> 
> ## Eigenvalues of the original matrix, A:
>> L <- eigen(A)$values
>> L
> [1] 200.5575446   0.4698347 -63.0273793
> 
> ## Eigenvalues of perturbed matrix, A':
>> L_prime <- eigen(A_prime)$values
>> L_prime
> [1] 200.5577974 -63.0262011   0.4698638
> 
> ## In comparing the eigenvalues of A and A',
> ## we need to be careful about ordering them.
>> L <- sort(L)
>> L
> [1] -63.0273793   0.4698347 200.5575446
>> L_prime <- sort(L_prime)
>> L_prime
> [1] -63.0262011   0.4698638 200.5577974
>> dL_computed <- L_prime - L
> 
> ## Actual change in eigenvalues between
> ## A and A' = A + dA:
>> dL_computed
> [1] 1.178222e-03 2.908929e-05 2.527263e-04
> 
> ## First-order change in eigenvalues computed
> ## with hum9's theorem; the changes are on
> ## the diagonal elements of the matrix below,
> ## which requires only the perturbations and
> ## the (orthogonal) eigenvectors of the original
> ## matrix:
>> CT %*% dA %*% C
>                [,1]          [,2]          [,3]
> [1,]  2.527263e-04 -1.760979e-05 -0.0001129474
> [2,]  6.090657e-05  2.908421e-05  0.0003997496
> [3,] -1.419097e-04  8.067480e-04  0.0011782275
>>
> ---------------------------
> 
> Yes, the diagonal elements of C^T * dA * C match
> the computed change in eigenvalues, for this real
> symmetric matrix, A.
> 
> 
> Krishna
> 

Thank you for support and for inspiration! :)

I reformulated that theorem so it looks now:

If real NxN matrix [A] has N orthonormal eigenvectors,
with matrix [C] of orthonormal eigenvectors as columns.

In the case of small perturbation of [A], for every
unperturbed eigenvector {x} corresponds an perturbed
eigenvector {x+dx} collinear with {x}.

Changing basis by [C] to a small perturbed version of [A]
will result an slight perturbed diagonal matrix with small
perturbed eigenvalues on its diagonal.

Have a nice day,
hum9

Thread

fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-10 10:29 -0700
  Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-12 05:41 -0700
    Re: fast matrix determinant mhx@iae.nl - 2017-06-12 06:03 -0700
      Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-12 07:14 -0700
        Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-12 07:28 -0700
        Re: fast matrix determinant mhx@iae.nl - 2017-06-12 11:21 -0700
          Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-12 16:39 -0700
        Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-14 18:05 +0300
          Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-14 11:05 -0700
            Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-14 21:37 +0300
          Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-15 09:59 +0300
            Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-15 03:30 -0700
              Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-15 17:57 +0300
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-15 19:06 -0700
                Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-16 10:21 +0300
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 03:38 -0700
                Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-16 15:58 +0300
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 06:04 -0700
                Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-16 16:19 +0300
                Re: fast matrix determinant mhx@iae.nl - 2017-06-16 03:58 -0700
                Re: fast matrix determinant albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-06-16 13:39 +0200
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 05:58 -0700
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 05:12 -0700
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 05:40 -0700
                Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-16 17:50 +0300
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-16 13:39 -0700
                Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-17 10:01 +0300
                Re: fast matrix determinant mhx@iae.nl - 2017-06-17 01:31 -0700
                Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-17 15:24 -0700
            Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-15 17:59 +0300
          Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-16 10:11 +0300
            Re: fast matrix determinant hum9 <obi65537@gmail.com> - 2017-06-17 09:20 +0300
      Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-13 16:43 -0700
        Re: fast matrix determinant mhx@iae.nl - 2017-06-13 22:04 -0700
        Re: fast matrix determinant mhx@iae.nl - 2017-06-14 12:23 -0700
          Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-14 18:31 -0700
    Re: fast matrix determinant krishna.myneni@ccreweb.org - 2017-06-15 19:13 -0700

csiph-web