sponsored links 

5
17th May 05:25
External User
Posts: 1

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 
7
17th May 05:25
External User
Posts: 1

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 azby, bwax, czdy, dwcx 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 
9
18th May 21:39
External User
Posts: 1

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] + [p1,q1], and we have the factorization [ 1 p1 ] [ e f ] [ pe pf ] [ 1 q1 ] [ 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 
10
18th May 21:39
External User
Posts: 1

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 