the term rank of a matrix

Discrete Math.Appl.,V ol.15,No.2,pp.171–177(2005)

?VSP2005.

A probabilistic algorithm for?nding the term rank of non-negative matrices

D.A.KUROPATKIN

Abstract—We suggest a probabilistic algorithm for?nding the term rank of a matrix with non-negative elements,?nd an estimate of the complexity of the algorithm,and establish an upper bound for the probability of?nding a wrong value of the term rank.

1.INTRODUCTION

In monograph[1],it is pointed out that one of the main global combinatorial characteristics of a matrix is the term rank.Section3of Chapter2in[1]is devoted to the estimation of the term rank of a matrix with non-negative elements.

In this research,we suggest a probabilistic algorithm for?nding the term rank of a matrix with non-negative elements.In Section2,the main de?nitions are introduced.In Section3,we describe the algorithm and give an estimate of the complexity of the algorithm. In Section4,the required proofs are presented.

In the suggested algorithm,the calculation of the term rank reduces to a repeated calcu-lation of the rank of some matrix similar to the initial one.This approach is based on the well-known idea(see,for example,[2])of?nding the permanent of a matrix via the determ-inant of some other matrix.Recall that in the general case the calculation of the permanent of a matrix cannot be reduced to calculation of the determinant of a matrix derived from the initial one by a linear transformation.

2.THE MAIN DEFINITIONS

We follow the system of notation and de?nitions of book[1].We say that A is a matrix of size m×n or an m×n matrix if it has m rows and n columns.Everywhere below we assume that m≤n.A matrix with non-negative elements is called non-negative.The set of all non-negative m×n matrices is denoted by?+m,n or?+n if m=n.The set of all m×n matrices over the?eld of real numbers is denoted by?m,n or?n if m=n.The set of natural numbers(positive integers)is denoted by N,and N k s stands for the set of all vectors of length k with elements1,...,s.

Originally published in Diskretnaya Matematika(2005)17,No.1,147–156(in Russian). Received March11,2004.

172 D.A.Kuropatkin

Let A=(a i,j)be a non-negative matrix of size m×n.The support of the matrix A is the(0,1)-matrix(a i,j)of size m×n with elements

a i,j=

1if a i,j=0, 0if a i,j=0.

De?nition1.The term rank of a matrix A is the maximal number of non-zero elements of A such that none two of them lie in one row or one column.

The term rank of a matrix A is denoted byρ(A).Two elements of a matrix are called collinear if they lie either in one row or in one column.A diagonal of an m×n matrix is a set of min(m,n)pairwise non-collinear elements of A.A diagonal consisting of non-zero elements is called non-zero.A partial diagonal of an m×n matrix is a set of non-zero pairwise non-collinear elements of the matrix,the number of which is less than min(m,n). Sometimes by a diagonal of a matrix is meant a non-zero diagonal.It will be clear from the context what diagonal is under consideration.

The permanent per(A)of a matrix A=(a i,j)∈?m,n is the number

per(A)=

σ

a1σ(1)a2σ(2)...a mσ(m),

where the summation is over all ordered tuplesσ=(σ(1),...,σ(m))consisting of m different elements of the set{1,...,n}.

De?nition2.The term rank of a matrix A is the maximal size of square submatrices with zero permanent.

It is clear that the two de?nitions of the term rank are equivalent.

3.ALGORITHM FOR FINDING THE TERM RANK

Let A=(a i,j)be a matrix in?+m,n which has exactly k non-zero elements.In this section, we describe a probabilistic algorithm for?nding the term rankρ(A).

Let

L(A)={(i,j),1≤i≤m,1≤j≤n:a i,j=0},

and let x be a vector consisting of k variables(x i,j),where the indices(i,j)∈L(A).We denote the ring of polynomials of k variables(x i,j)over the?eld of real numbers by R[x]. Further,the ring of matrices of size m×n over this ring of polynomials is denoted by R[x]m,n.

We call a matrix B A(x)in R[x]m,n the associated matrix for the matrix A if the element of B A(x)located in the i th row and in the j th column is equal to x i,j if a i,j>0and to0 if a i,j=0.Here the symbol x,as in the previous paragraph,denotes the vector consisting of k variables x i,j.It is clear that the supports of the matrices A and B A(x)coincide.For an arbitrary vector d∈N k s,we de?ne the matrix B A(d)in the natural way:we replace the components of the vector x sequentially,beginning with the elements of the?rst row,by the

A probabilistic algorithm for?nding the term rank173 components of the vector d.An arbitrary vector d∈N k s is called a root of the polynomial det

B A(x)if det B A(d)=0.

In the description and the functioning of the algorithm,two parameters,l and s take part.They are input parameters,and their values are prescribed in advance,before the start of algorithm operation.Their role will be clari?ed in the description of the algorithm.Here we only say that their choice in?uences the probability of?nding the right value of the term rank of a matrix by the algorithm.It will be seen from the further assertions that the greater are the values of these parameters,the greater is the probability that the algorithm?nds the right value of the term rank of a matrix.

Algorithm.(1)Assign the value1to the variable i.

(2)Choose a vector d(i)in N k s with equal probabilities.

(3)Find the rank of the matrix B A(d(i)).This can be done,for example,by reducing

the matrix B A(d(i))to the row-echelon form by the Gaussian elimination algorithm

(a description of this algorithm can be found,for example,in[3]).Let this rank be

equal to r(i).

(4)If the value of the variable i is less than the value of the parameter l,then we in-

crease the value of i by one and go to step2.If i=l,then we?nd the value of ρ (A)=max{r(1),...,r(l)}and declare thatρ (A)is the required value ofρ(A).

Below we will say that a mistake happen in the operation of Algorithm ifρ (A)=ρ(A) for a matrix A which is fed to the input of Algorithm.

Proposition1.Let a matrix A belong to?+m,n and s>2.Then

(1)ρ (A)≤ρ(A);

(2)the probability of mistake in the operation of Algorithm(ρ (A)=ρ(A))is estimated

as follows:

P(ρ (A)=ρ(A))≤

2

s

l

.

Proposition2.For any matrix A belonging to?+m,n the number of additions and mul-tiplications of rational numbers executed by Algorithm is O(nm2).

4.THE PROOFS

Let A be a matrix with k non-zero elements which belongs to?n and let a1,1=0.We denote by F the matrix obtained from A by erasing the?rst row and the?rst column and by G the matrix obtained from A by replacing the element in the entry(1,1)by zero. For any real vector d=(d i,j),(i,j)∈L(A),we denote by d1the vector(d i,j),where (i,j)∈L(A)and either i=1or j=1,and by d2the vector(d i,j),where(i,j)∈L(A) and(i,j)=(1,1).Thus,the vectors d1and d2are parts of the vector d.

174 D.A.Kuropatkin

Lemma1.Let A be a matrix with k non-zero elements which belongs to?n and sat-is?es the following condition:there exists a vector d?=(d?i,j),(i,j)∈L(A),of length k with real elements such that det B A(d?)=0.

Then there exists a vector d=(d i,j),(i,j)∈L(A),belonging to N k s,s>1,such that det B A(d)=0.

Proof.We prove the lemma by induction on the number k of non-zero elements of the matrix A.

In the case k=2,the assertion of the lemma is obvious.Indeed,in this case,by the conditions of the lemma,the matrix A has the size at most2×2,and the two non-zero elements must be placed either in the entries(1,1)and(2,2)or in the entries(1,2)and (2,1).Then it is clear that it is possible to choose a vector d in N k s,s>1,such that det B A(d)=0.

Let the assertion of the lemma be true for any matrix A with exactly k?1non-zero elements.Consider the case where the matrix A has exactly k non-zero elements.It follows from the conditions of the lemma that the?rst row of the matrix B A(x)has at least one non-zero element.Without loss of generality we assume that the entry(1,1)contains the non-zero element x1,1.It is obvious that for any real vector d=(d i,j),(i,j)∈L(A),the representation

det B A(d)=d1,1det B F(d1)+det B G(d2)(1) is true.Recall that F,G,d1,and d2are de?ned in this section ahead of the formulation of Lemma1.

Since there exists a real vector d?of length k such that det B A(d?)=0,the equalities det B F(d?1)=0and det B G(d?2)=0cannot be satis?ed simultaneously.

Without loss of generality we assume that det B F(d?1)=0.By the induction hypothesis the set N k s contains a vector c=(c i,j),(i,j)∈L(F),such that det B F(c)=0.Then consider an arbitrary vector d2=(d i,j),(i,j)∈L(G),such that for j=1,(1,j)∈L(A) the element d1,j is an arbitrary number of the set N1s,for i=1,(i,1)∈L(A),the element d i,1is also an arbitrary number of the set N1s,and d i,j=c i?1,j?1if i>1,j>1,(i,j)∈L(A).Thus,we consider the vector d2whose components coincide with the corresponding components of the vector c.It is clear that for the described vector d2there exists d1,1∈N1s such that det B A(d)=0,where d=(d i,j),(i,j)∈L(A).The case where det B G(d?2)=0, is considered in the same way.

The lemma is proved.

Lemma2.Let s≥1,and let a matrix A belong to?n,have k non-zero elements and satisfy the following condition:there exists a vector d?=(d?i,j),(i,j)∈L(A),with real element such that

det B A(d?)=0.

Then the number X A of the vectors d=(d i,j),(i,j)∈L(A),belonging to the set N k s and such that

det B A(d)=0,

satis?es the inequality

X A≤2s k?1.

A probabilistic algorithm for?nding the term rank175

Proof.Let d=(d ij),(i,j)∈L(A),be a vector belonging to the set N k s and such that det B A(d)=0.We denote the i th row of the matrix B A(d),i=1,...,n,by b i(A,d). Since det B A(d),the rows of the matrix B A(d)are linearly dependent,that is,there exists a set of real numbers c i,i=1,...,n,not all equal to zero,such that

n

i=1

c i b i(A,d)=0.(2)

Without loss of generality we assume that c1=0.Since there exists a vector with real elements d?=(d?i,j),(i,j)∈L(A),such that det B A(d?)=0,not all elements d1,j, (i,j)∈L(A),are equal to zero.Let d t,1=0,t∈{1,...,n}.Then it follows from(2)that

n

i=1c i d i,1=0,d t,1=?

1

c1

n

i=1,i=t

c i

d i,1.

Thus,the last equality means that if d=(d i,j),(i,j)∈L(A),is a vector such that det B A(d)=0,then one of the elements(in this case,d t,1)can be represented in terms of the remaining elements.Therefore,the total number of such vectors cannot be greater than s k?1.

The lemma is thus proved.

Remark1.Experimental data show that for small k and n the number X A of roots is less than s k?1,and with increase of k and n the difference between the estimate given in Lemma2and the true value increases.

Lemma3.Let s>1,and let the matrix A belong to?+m,n and have k non-zero ele-ments.Then the equality

ρ(A)=max

d∈N k s

rank B A(d),(3) is true,here rank B A(d)is the rank of the matrix B A(d).

Proof.Recall that the rank of a matrix is the maximal size of a square submatrix with non-zero determinant.The determinant is a linear combination with coef?cients equal to 1or?1of all numbers each of which is the product of all elements of some diagonal of the submatrix.According to De?nition2the term rank of a matrix is the maximal size of the square submatrix with non-zero permanent.The permanent is the sum of all numbers each of which is a product of all elements of some diagonal of the submatrix.Thus,the difference between the de?nitions of the rank and the term rank consists of the fact that it is needed to check the equality to zero of a linear combinations of some numbers in the?rst case and of the sum of the same numbers in the second case.

Let us prove the inequality

ρ(A)≥max

d∈N k s

rank B A(d).(4)

For an arbitrary matrices F and G belonging to?+m,n with identical supports,the in-equalityρ(F)≥rank(G)is true.Since the supports of the matrices A and B A(d)coincide

176 D.A.Kuropatkin

for any d∈N k s,for any such d the inequalityρ(A)≥rank B A(d)is true.Hence it follows that inequality(3)is true.

Let us prove the inverse inequality

ρ(A)≤max

d∈N k s

rank B A(d).

Letρ(A)=p.It follows from the de?nition of the term rank that there exists a p×p submatrix H of the matrix A with non-zero permanent.We denote the number of non-zero elements of the matrix H by i.There exists a vector d?of length i with real elements such that det B H(d?)=0.Indeed,the determinant of the matrix B H(x)is a polynomial of i variables.Since per H=0,the polynomial det B H(x)is non-zero and is a linear combina-tion of monomials of length p.Therefore,there exists a vector d?with real elements such that det B H(d?)=0.Then by Lemma1there exists a vector d∈N i s,s>1,such that det B H(d)=0.

We choose a vector f∈N k s such that the components of the vector d are located on the corresponding places of f.Then it is clear that rank B A(f)≥l.Therefore,

p≤max

d∈N k s

rank B A(d).

Thus,the inequality inverse to(4)is proved,and the validity of equality(3)is established.

The proof of the lemma is completed.

Proof of Proposition1.It follows from Lemma3that the term rank of a matrix is equal to the maximal rank of the associated matrix over all vectors in N k s.Algorithm?nds the maximal rank of the corresponding matrix only over l vectors in N k s.Hence it follows that

ρ (A)≤ρ(A).

If max d∈N k

s rank B A(d)is equal to p,then there exist a vector d in N k s and a p×p

submatrix H(d)of the matrix B A(d)such that det H(d)=0.Let the matrix H(d)contain v non-zero elements.Let for some vector d(i),i=1,...,l,appearing in Algorithm the determinant of the matrix H(d(i))be not zero.Then rank B A(d(i))≥l,and consequently,ρ (A)≥ρ(A).Taking into account the inequality obtained in the previous paragraph,we see thatρ (A)=ρ(A).

Thus,the probability that Algorithm makes a mistake(that is,ρ (A)=ρ(A))can be estimated from above by the probability that for any i=1,...,l the determinant of the matrix H(d(i))is equal to zero.With the use of Lemma2the last probability can be estimated from above by the value(2s v?1/s v)l=(2/s)l.

Proposition1is proved.

Remark2.It follows from the proof of Proposition1that the less the estimate of the number X A of the roots the less the probability of the mistake of Algorithm for?xed para-meters s and l.Experimental data show that Algorithm operates better than it follows from the estimate given in Proposition1.In other words,in fact the probability that Algorithm makes a mistake is less than the bound given in Proposition1.

Proof of Proposition2.This assertion is obvious.Indeed,the complexity of Algorithm is equal,in fact,to the complexity of?nding the rank of a matrix multiplied by l.In this case,for?nding the rank we use the Gaussian algorithm whose complexity is O(nm2).

A probabilistic algorithm for?nding the term rank177

Remark3.Estimating the complexity of Algorithm we assume that the parameters s and l are?xed,and only the parameters n and m tend to in?nity.Therefore,estimating the complexity,we give only the order of the upper estimate tending to in?nity and nothing is said about the dependence of the estimate on s and l.

The Gaussian algorithm is not optimal for?nding the rank of a https://www.sodocs.net/doc/832633157.html,ing more fast algorithms can re?ne the estimate of complexity of Algorithm.For example,paper[4] contains a description of an algorithm for?nding the rank of a matrix whose complexity is O(nm log27?1).From the aforesaid it follows that the complexity of the modi?ed Algorithm is also O(nm log27?1).

REFERENCES

1.V.N.Sachkov and V.E.Tarakanov,Combinatorics of Nonnegative Matrices.American Math.

Soc.,Providence,RI,2002.

2.H.Minc,Permanents.Addison–Wesley,Reading,MA,1978.

3. D.K.Faddeev and V.N.Faddeeva,Computational Methods of Linear Algebra.Fizmatgiz,Mo-

scow,1960(in Russian).

4.V.I.Solodovnikov,Upper bounds on the complexity of solving systems of linear equations.J.

Sov.Math.(1985)29,1482–1501.