Mombu the Science Forum sponsored links

Go Back   Mombu the Science Forum > Science > Is there a simple way to see if a matrix can be factorized
User Name
Password
REGISTER NOW! Mark Forums Read

sponsored links


Reply
 
1 4th May 20:11
larry hammick
External User
 
Posts: 1
Default Is there a simple way to see if a matrix can be factorized


"ieee std"

If we're talking only of square matrices, det(A) will have to be equal to
det(B)det(C). Better, the characteristic polynomial of A will be the product
of the c.p.'s of B and C.
But you might want to clarify just what is meant by "factorization". E.g. if
B is invertible (e.g. a 0-1 matrix representing a permutation) then we can
always "factor" A as A=BDB^{-1} simply by setting
D=B^{-1}AB.
LH
  Reply With Quote


  sponsored links


2 5th May 15:23
hsjameson
External User
 
Posts: 1
Default Is there a simple way to see if a matrix can be factorized


(For which 2x2 matrices A can we find 2x2 matrices B, C with positive
integer entries such that A = BC?)

If we simply require the elements of B and C to be positive, not
necessarily positive integers, the problem is simple.

Let A = [ a1 a2 ] for ease of notation
[ a3 a4 ]

If any element of A is nonpositive then it is clearly imposssible for
all entries of B and C to be positive.

On the other hand, if all of the elements a1, a2, a3, a4 of A *are*
positive, we can let B be a positive perturbation of the identity
matrix, guaranteeing that the matrix C is sufficiently close to A that
it is itself positive.

********ly, let B be the perturbed identity matrix

[ 1 d ]
[ d 1 ]

where 0 < d < 1 is strictly less than min(a1/a3, a3/a1, a2/a4, a4/a2),
and let C be the matrix

1/(1 - d^2) * [ a1 - d*a3 a2 - d*a4 ]
[ a3 - d*a1 a4 - d*a2 ]

Now, since 1/(1 - d^2) > 0, all the entries of C are positive from the
definition of d (for instance, we can be certain that a1 - d*a3 > 0
since this is equivalent to d < a1/a3). The form of C can be found
directly by inverting the matrix B and calculating B^(-1)A.

It is simple to confirm that the product BC is equal to the original
matrix A. Moreover, this result may be generalised to higher
dimensions: for instance, given a 3x3 matrix A with positive entries,
choose B to be the matrix

[ 1 d d ]
[ d 1 d ]
[ d d 1 ]

This matrix is certainly invertible for 0 < d < 0.5, and we can find a
suitable d simply by computing C = B^(-1)A as a function of d, and
decreasing d towards zero until C is sufficiently close to A that it
is a positive matrix.

HJ
  Reply With Quote
3 6th May 15:02
ieeestd802
External User
 
Posts: 1
Default Is there a simple way to see if a matrix can be factorized


Thanks for all reply.
The original post is to seek A= BC where each element of A, B, C
is positive integer.

Is it a simple way to do this ?
  Reply With Quote
4 8th May 05:40
dgoncz
External User
 
Posts: 1
Default Is there a simple way to see if a matrix can be factorized


If A has no coprime elements? Maybe.

If the elements of A are pairwise coprime? I don't think so.

Can anyone confirm?

Yours,

Doug Goncz, Replikon Research, Seven Corners, VA
Unequal distribution of apoptotic factors regulates
embryonic neuronal stem cell proliferation
Hey, it's a news group! So that's the news!
  Reply With Quote
5 17th May 05:25
israel
External User
 
Posts: 1
Default Is there a simple way to see if a matrix can be factorized


What, you mean like

[ 5 9 ] [ 1 2 ] [ 1 1 ]
[ 7 11 ] = [ 3 2 ] [ 2 4 ] ?

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
  Reply With Quote
6 17th May 05:25
larry hammick
External User
 
Posts: 1
Default Is there a simple way to see if a matrix can be factorized


"Larry Hammick"
....


Oops, sorry, that needs a bit of work. But you get the idea The traces
add, at least.
LH
  Reply With Quote
7 17th May 05:25
israel
External User
 
Posts: 1
Default Is there a simple way to see if a matrix can be factorized


Maybe not really simple, but it's a finite search.

Let's say

[ a b ] [ s t ] [ w x ]
A = [ c d ], B = [ u v ], C = [ y z ]
Note that a + c = sw + ty + uw + vy = (s+u)w + (t+v)y >= 2 (w+y)
and similarly b + d >= 2 (x + z). So search through all 2 x 2
matrices C of positive integers whose column sums are at most half the
corresponding column sums of A, checking whether A C^(-1) is a matrix
of positive integers, i.e. whether each of az-by, bw-ax, cz-dy, dw-cx
is a positive multiple of det(C).

The search might be cut down significantly.
First note that we may assume det(C) > 0, since if B and C are a solution
then so are BJ and JC where

[ 0 1 ]
J = [ 1 0 ]

Moreover, det(C) must divide det(A).
We want az - by > 0 and c z - d y > 0 so z > max(b/a, d/c) y, and
similarly x < min(b/a, d/c) w.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
  Reply With Quote
8 18th May 01:45
dgoncz
External User
 
Posts: 1
Default Is there a simple way to see if a matrix can be factorized


A counterexample to my:


I bow before you, sir. That is to say, I have inspected your counterexample and
found it surprising and correct.

Let's see:

Perhaps it will be true that:

If A is a matrix of unique primes or is pairwise coprime,

and B and C contain no factors of any number in A, and with special
consideration for 1, which is not a prime, but can be a factor, and cannot be
coprime to anything;

Then A # B*C, and we have a new cryptographic method with public key one of A,
B, or C, and private key one of the others?

What is the strength of this method, and how does it increase with rank?

Copy to sci.crypt? I can't do that with aol.

Yours,

Doug Goncz, Replikon Research, Seven Corners, VA
The hormones work at different speeds. In a fight-or-flight scenario,
glucocorticoids are the ones drawing up blueprints for new aircraft carriers;
epinephrine is the one handing out guns.
  Reply With Quote
9 18th May 21:39
israel
External User
 
Posts: 1
Default Is there a simple way to see if a matrix can be factorized


That posting of mine assumed det(C) <> 0. The case where det(A) = 0
is rather
special and should be dealt with separately. In fact, this case is
easy.

Again I'll write

[ a b ] [ s t ] [ w x ]
A = [ c d ], B = [ u v ], C = [ y z ], A = B C,

where all entries are positive integers, and I'm assuming det(A) = 0.
So det(B) = 0 or det(C) = 0. WLOG assume it's det(C) = 0 (otherwise
do the same ****ysis on A^T = C^T B^T). Then I claim the necessary
and sufficient condition to factor A is gcd(a,b) > 1 and gcd(c,d) > 1.

The columns of C are parallel. Writing w/y = x/z = m/n in lowest
terms, we have [w, y] = e [m, n] and [x, z] = f [m, n] where e,f,m,n
are positive integers. Then [a,c]^T = B [w,y]^T = e B [m,n]^T and
similarly [b,d]^T = f B [m,n]^T. Let [p,q]^T = B [m,n]^T, so p and
q are positive integers with a = p e, c = q e, b = p f, d = q f. Now
[p, q] = m [s, u] + n [t, v]. In particular p >= 2 and q >= 2, so
gcd(a,b) >= 2 and gcd(c,d) >= 2.
Conversely, suppose gcd(a,b) = p > 1 and gcd(c,d) = q > 1. Then
(using the fact that [a,b] and [c,d] are parallel) we can write
[a,b] = p [e,f] and [c,d] = q [e,f]. Then we can
write [p,q] = [1,1] + [p-1,q-1], and we have the factorization

[ 1 p-1 ] [ e f ] [ pe pf ]
[ 1 q-1 ] [ e f ] = [ qe qf ] = A

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
  Reply With Quote
10 18th May 21:39
israel
External User
 
Posts: 1
Default Is there a simple way to see if a matrix can be factorized


[3 8] [3 5] [73 127]
[5 8] [8 14] = [79 137]

Note that all entries of A are prime.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
  Reply With Quote
Reply


Thread Tools
Display Modes




Copyright 2006 SmartyDevil.com - Dies Mies Jeschet Boenedoesef Douvema Enitemaus -
666