liushunyi

35 Reputation

5 Badges

5 years, 109 days

MaplePrimes Activity


These are questions asked by liushunyi

Hi all,

Let $A$ be a 0-1 square matrix of order $n$. I want to obtain a matrix $D$ from powers $A$, $A^2$, $\dots$, $A^{n-1}$, where the ($i,j$)-element of $D$ is the smallest $k$ for which the ($i,j$)-element of $A^k$ is nonzero. I only consider the non-diagonal elements of $D$.For example, if the matrix $A$ is Matrix( [[0, 1, 0, 0, 0], [1, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0]]), then $D$ shoule be Matrix([[0, 1, 2, 3, 4], [1, 0, 1, 2, 3], [2, 1, 0, 1, 2], [3, 2, 1, 0, 1], [4, 3, 2, 1, 0]]). However, I cannot obtain this result.

The code is as follows.

p := proc ()

   local A, B, D, m, n, k, r;

   A := Matrix([[0, 1, 0, 0, 0], [1, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0]]);

   r := LinearAlgebra:-RowDimension(A);

   D := A;

   for k from 2 by 1 to r-1 do

       B := A^k;

       for m from 1 by 1 to r do

           for n from 1 by 1 to r do

               if m <> n and B[m, n] <> 0 and D[m, n] = 0 then

                    D[m, n] := k

                end if;

           end do;

        end do;

   end do;

   D;

end proc;

By executing this procedure, I obtain D=Matrix([[0,1,2,3,3],[1,0,1,2,3],[2,1,0,1,2],[3,2,1,0,1],[3,3,2,1,0]]), which is not I want.

Thanks.

The permanent of a square matrix is defined similarly to the determinant, as a sum of products of sets of matrix entries that lie in distinct rows and columns. However, where the determinant weights each of these products with a ±1 sign based on the parity of the set, the permanent weights them all with a + 1 sign.While the determinant can be computed in polynomial time by Gaussian elimination, the permanent cannot. Valiant has showed that computing permanents is #P-hard, and even #P-complete for matrices in which all entries are 0 or 1 [L.G. Valiant, The Complexity of Computing the Permanent, Theoretical Computer Science 8 (1979) 189–201]. The development of both exact and approximate algorithms for computing the permanent of a matrix is an active area of research. (see Wikipedia: computing the permanent, more details on permanent)

The best known general exact algorithm is due to H. J. Ryser (1963) [Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus mathematical monographs, The Mathematical Association of America. Ryser formula ]. Ryser's formula can be evaluated using O(2^{n}*n^2) arithmetic operations, whereas O(n!*n) arithmetic operations if we compute the permanent using the definition.

There have been codes of Ryser's algorithm for computing the permanent written in C language and Matlab. I cannot find a Ryser's procedure in Maple. So I try to write a Maple procedure to compute the permanent using Ryser's algorithm. The code is as follows:

permanentRyser := proc (M::Matrix) 
      local S, T, B, m, n, s, i, j, rowsum, sum, prod, perm;
      m, n := op(1, M);
      if m <> n then
               error "expecting a square Matrix, got dimensions %1, %2", m, n
      end if;
      rowsum := 0;
      sum := 0;
      prod := 1; 
      S := combinat:-subsets([seq(1 .. m)]);
      Snextvalue();
      while not Sfinished do
             T := Snextvalue();
             s := numelems(T);
             B := LinearAlgebra:-SubMatrix(M, [1 .. m], T);
             for i to m do
                  for j to s do
                          rowsum := rowsum+B[i][j];
                 end do;
                 prod := prod*rowsum; 
                 rowsum := 0;
             end do; 
            prod := (-1)^s*prod;
            sum := sum+prod;
            prod := 1 ;
      end do;
      perm := expand((-1)^m*sum) ;
end proc:
The last second statement "perm := expand((-1)^m*sum) ;" I mean to compute the permanent of  a matrix containing a variable, e.g. the characteristic matrix. If the matrix is numeric, then "expand" should be deleted.

Now I have two questions:

1. Suppose that A is random matrix of order 20, the time(permanentRyser(A)) is about 716 seconds and time(LinearAlgebra:-Permanent(A)) is about 66 seconds. We can see that LinearAlgebra:-Permanent(A) is much faster than permanentRyser(A).  I don't know whether the code I written is accurate and efficient. Thanks to anyone who gives a more efficient procedure of computing the permanent using Ryser's formular.

2. The source code of the function permanent is as follows.

proc (A::(`~Matrix`(square)), ` $`)
     option `Copyright (c) 1999 Waterloo Maple Inc. All rights reserved.`;
     local m, n, t1;
     m, n := op(1, A);
     if m <> n then
              error "expecting a square Matrix, got dimensions %1, %2", m, n
     end if;
     if n = 1 then t1 := A[1, 1] ;
     else
            tools/ClearRememberTable(Permanent/pminor`);
            t1 := [`$`(1 .. n)];
            t1 := Permanent/pminor(A, t1, t1, n)
      end if
end proc

I cannot understand the source code. Does the source code compute the permanent by Laplacian expansion? If the LinearAlgebra:-Permanent() compute the permanent by Laplacian expansion, then it should take more time than by using Ryser's algorithm.

Thanks all.

I have two questions and I don't know whether it can be solved using Maple. The first question is that I have a text file, the data of which has been sorted using Unix procedure SORT. Since the data has been sorted, we just need to compare consecutive lines. Our aim is to count the total number of the same lines of this file and obtain the maximum number of the same consecutive lines. For example, the data of the file, named file.txt, is:

1,0,5,-2,2,0
1,0,5,-2,3,0
1,0,5,-2,4,-2
1,0,5,-4,4,0
1,0,5,-4,4,0
1,0,5,-4,4,0
1,0,5,0,5,-2
1,0,5,0,6,0
1,0,5,0,6,0

I want to get two numbers: the total number of the same lines 5 and the maximum number of the same consecutive lines 3. Another question is, given a string s, if s is not contained in this file, then the program returns NULL;otherwise, the program returns the total number it appears and the specific line numbers it appears. For instance, suppose the string is s=1,0,5,-4,4,0, then it returns the total number 3 and the line numbers 4,5,6.

Best regards,

Liu

I have a polynomial p in two variables x and y, and I want to extract all the coefficients of p. For example, let p:=x^3+2*x*y^2-2*y^2+x, and I want to obtain the coefficient vector [1,0,0,1,0,2,0,0,-2,0], where 1,0,0,1,0,2,0,0,-2,0 are respectively the coefficients of x^3, x^2, x^2*y,x,x*y,x*y^2,y^0,y,y^2,y^3. In general, let 

p(x,y)=sum(sum(c_*{i, j}*x^(n-i)*y^j, j = 0 .. i), i = 0 .. n)

=c_{0,0}x^n

+c_{1,0}x^{n-1}+c_{1,1}x^{n-1}y

+c_{2.0}x^{n-2}+c_{2,1}x^{n-2}y+c_{2,2}x^{n-2}y^2

+\dots

+c_{n,0}+c_{n,1}y+c_{n,2}y^2+\dots+c_{n,n}y^{n}.

It is possible that some coefficients c_{i,j} are equal to 0. How to obtain the coefficient vector [c_{i,j},i=0..n,j=0..i] of p(x,y)?

Thanks a lot.

Dear all,

I want to compute the charateristic polynomials of some matrices (the number of matrices is more than 10000), and write the coefficients of the resulting polynomials to a text file. The entries of the given matrices are stored in a text file. More specifically, suppose that M_1, M_2 and M_3 are three matrices, and the entries of them are stored in a text file named "data.txt" in the following form:

1 2 3

4 5 6

7 8 9

 

1 -1 0

2 3 6

-3 0 2

 

2 1 -1

1 -1 -2

0 1 2

The resulting output file should be of the following format:

1, -15, 18, 0

1, -6, 13, -28

1, -3, 1, 3

I don't know how to repeatedly read the data from the given text file. I think the procedure should be as follows.

>restart:

>with(LinearAlgebra):

>with(FileTools:-Text):

>fid:=Open("data.txt"):

>fid_1:=Open("data_1.txt"): #data_1 is the output file

>ReadFile(fid); #since the number of matrices is very large, I want the data to be read once

>numlines:=CountLines(fid);

>for i from 1 to numlines do

       here I need repeatedly read the data to a matrix M (I don't know how to do);

       P:=CharacteristicPolynomial(M,x);

       writedata[APPEND]("data_1.txt",map(i-> coeff(p, x, i), [seq(i, i = 0 .. degree(p, x))]));  #this statement cannot write the coefficients of a polynomial in the same row

>end do;

>Close(fid):

>Close(fid_1):

Now as I'm pretty new to Maple, I don't know any better and can't seem to get any information out of the help documents. 

Thanks a lot.

1 2 Page 1 of 2