What properties does the coefficient matrix B satisfy? For instance, if B is of full column rank, then the vector e should be zero.

B is an incidence matrix, thus each column should have +1 and -1. If vector e is not constrained, we can easily get the null space of B. Vector e is constrained to have certain similar values. For instance, e1 = e4 = e5, e2=e3, e6=e7 and so on. I don't like trivia solutions that ei =0 for all i because I can compute the solution algebraically. What I am not sure is the linear algebra solution.

This is my answer from yesterday!

You should add rows to your matrix B and solve it as "unconstrained" system of homogeneous linear equations. In your example you should add rows r1, r2, r3, r4 and so on, where

r1 = (1 0 0 -1. ..), r2 = (0 0 0 1 -1. ..), r3=(0 1 -1. ..), r4= (0 0 0 0 0 1 -1), ...

You have matrix B' which is

B

1 0 0 -1 0 0 0

0 0 0 1 -1 0 0

0 1 -1 0 0 0 0

0 0 0 0 0 1 -1

in case number of variables is 7

and solve

B'e=0

In case rank B' is equal to 7 (in your example, with seven variables)

the solution should be unique, e=0

:-)

Perhaps I did not make my question clearer.

I can show a counter example to illustrate that vector e is not always zero.

Suppose we have adjacency matrix of a graph

A=[0 1 1 0 0;

0 0 1 1 1;

0 0 0 1 0;

0 0 0 0 1;

1 0 0 0 0]

We convert the adjacency matrix into incidence matrix

edge: 12 13 23 24 25 34 45 51

B=[ 1 1 0 0 0 0 0 -1;

-1 0 1 1 1 0 0 0;

0 -1 -1 0 0 1 0 0;

0 0 0 -1 0 -1 1 0;

0 0 0 0 -1 0 -1 1]

The original vector is

e=[e12,e13,e23,e24,e25,e34,e45,e51]'

the constrained vector becomes

e=[x1,x1,x2,x2,x2,x3,x4,x5]'

These constrains represent the flow on the edges of the graph (as I want to make the flow equally divided by the

number of edges out of the vertices)

I can compute manually that

x1=3

x2=1

x3=4

x4=5

x5=6

so we have

e=[3,3,1,1,1,4,5,6]'

B*e = [0,0,0,0,0]' = 0

and you see that vector e is not zero.

The question is how to solve for constrained vector e using Linear Algebra such that B*e=0?

of course, not

you did not get my answer

it is always 0 only in the case rank B' is equal to number of variables!

My answer was published 1 day ago

0 is just one of the possibilities.

another example

e1=e2=e3=...=e7

Solution 11111 satisfies all your constraints

Please read my answer from yesterday again!

I have to go now.

I will write you later

just add extra rows to your matrix B.

I have shown it a day ago

Thanks Lucy for the answer but I don't quite understand how the extra rows in matrix will transform the constraint equation into unconstraint

Thanks a lot Peter and Lucy. This is probably new for me that we can remove constraint by adding zeros rows. All I know was adding zeros row does not actually change the rank of a matrix. Any books can you suggest for me to learn further on this type of problems?

@Lucy, Peter: I have read the two books you mentioned and could not find any topic regarding adding +1/-1 rows could transform constrained equation into unconstrained equation.

Do you have any other clue or perhaps example how do you transform constrained equation into unconstrained equation by adding +1/-1 rows?

You have system of linear homogeneous equations.

Be=0, where B is mxn matrix (with m rows and n columns), e -is n-vector.

I assume you know how to solve this system.

Just a reminder:

A non-zero solution for this system exists iff rank of matrix B is less then number of variables.

All solutions of this system form a subspace.

In case rank B is equal to n the subspace consists of 0 vector only.

In your example number of rows of matrix B is equal to 5, number of columns is equal to 8

B=[ 1 1 0 0 0 0 0 -1;

-1 0 1 1 1 0 0 0;

0 -1 -1 0 0 1 0 0;

0 0 0 -1 0 -1 1 0;

0 0 0 0 -1 0 -1 1]

So, in your example you have system of 5 linear homogeneous equations with 8 variables.

Also, you have additional constraints

"the constrained vector becomes

e=[x1,x1,x2,x2,x2,x3,x4,x5]"

I understand that you have constraints

e1=e2; e3=e4=e5.

Using your notationx

e1=e2=x1;

e3=e4=e5=x1, where e1, e2, e3, e4, e5, e6, e7, e8 are variables of the original problem

Be = 0, e=(e1, e2, e3, e4, e5, e6, e7, e8)., x1, x2 are parameters

Your original system is

e1+e2-e8=0

-e1+e3+e4+e5=0

-e2-e3+e6=0

-e4-e6+e7=0

-e5-e7+e8=0

Is it correct?

Do we speak common language?

If your answer is "yes" you can read further.

Otherwise stop and explain, please, what I do not understand in your problem formulation..

In case "yes".

Your additional constraints can be written in form of another system of linear homogeneous equations:

e1=e2; e3=e4=e5.

or

e1-e2=0,

e3-e4=0

e4-e5=0

This system with 8 variables e1, e2, , e8 is represented by another matrix of 3 rows and 8 columns

1 -1 0 0 0 0 0 0

0 0 -1 1 0 0 0 0

0 0 0 1 -1 0 0 0

Now add these rows to your original matrix B

You will get new matrix

B'=[ 1 1 0 0 0 0 0 -1;

-1 0 1 1 1 0 0 0;

0 -1 -1 0 0 1 0 0;

0 0 0 -1 0 -1 1 0;

0 0 0 0 -1 0 -1 1

1 -1 0 0 0 0 0 0

0 0 -1 1 0 0 0 0

0 0 0 1 -1 0 0 0]

Now you have system of 8 linear homogeneous equations with 8 variables

B'e=0

or

e1+e2-e8=0

-e1+e3+e4+e5=0

-e2-e3+e6=0

-e4-e6+e7=0

-e5-e7+e8=0

e1-e2=0,

e3-e4=0

e4-e5=0

Once again, you have system of linear homogeneous equations.

Now I have questions.

What is the rank of original matrix B?

What is the rank of new matrix B'?

How are you going to solve this new system?

In general:

Is it possible that a system of linear homogeneous equations has non-zero solution,

still it does not have non-zero integer solution?

Ok, now I get it. It is not just +1/-1 rows as I misunderstood. Thanks a lot Lucy.

Dont worry about your last questions because I also have writen tutorial on linear algebra and wrote many online calculators on matrices as you can see on my web site http://people.revoledu.com/kardi/tutorial/LinearAlgebra/

I appreciate your excellent explanation. Thanks once again.

Adding rows to original matrix is just one of many possible ways of approaching your problem. The reason I asked all those questions:

In general (it depends on the structure of your additional constraints),

it may happen that the rank of your new matrix is less than number of variables,

still there is no integer nonzero solution!

It may happen, if, for example, your additional constraints contain irrational coefficients.

Also, the approach might not work at all if the nature of extra constraints is nonlinear.

F(e)=0,

where F is not necessarily linear operator.

In general, the restriction that you are looking for integer or 0-1 solution might need different approach: branch-and-bound, implicit enumeration, etc.

@ Peter and @ Lucy: I tested your solutions and I can confirm that they are working very well! Excellent! Thank you very much!

In the case of linear relations, and for B square (B can be a singular matrix). If you are interested in a graphical procedure to get an analytical solution to Be = 0, there is a result that you can apply using a bond graph in derivative causality assignment:

Gilberto Gonzalez, Rene Galindo, "Steady state determination using bond graphs for systems with singular state matrix", Proceedings of the Institution of Mechanical Engineers Part I: Journal of Systems and Control Engineering, vol. 225 (7), pp. 887-901, 2011, Professional Engineering Publishing. DOI: 10.1177/2041304110394552, http://pii.sagepub.com/content/early/2011/08/25/2041304110394552.abstract