Math Is Fun Forum

cathyli1109

Guest

Urgent -Discrete Math problems (Graph)

Hi,

I would like to ask 2 questions:

1)
Find all simple graphs of 8 vertices such that adjacency matrix is similar to its incident matrix.

2)
Let H is a simple connected graph with 6 vertices. How many possible graphs of H if H contains at least a vertex with odd degree.

Please help me.

Thank you so much!

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Urgent -Discrete Math problems (Graph)

Hi;

I hate definitions.

Please define similar?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,626

Re: Urgent -Discrete Math problems (Graph)

I can only think that similar means "have the same numbers in the same places".

If that is so, I'm not finding many graphs at all.

Trivial 1:  8 vertices completely disconnected.  Both matrices have zeros everywhere. 

Almost trivial 2:  Connect each point only to itself with a directed loop.  Both matrices have 1s on the leading diagonal and zeros elsewhere.

After that:  Hmmmm.  Still working on that.  Keep getting failures.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: Urgent -Discrete Math problems (Graph)

Almost trivial 2:  Connect each point only to itself with a directed loop.  Both matrices have 1s on the leading diagonal and zeros elsewhere.

http://en.wikipedia.org/wiki/Graph_(mat … mple_graph

As opposed to a multigraph, a simple graph is an undirected graph that has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices.

Also, http://en.wikipedia.org/wiki/Matrix_similarity.

The only thing I am able to think up about this problem is that the graph has to have exactly 8 edges.

Last edited by anonimnystefy (2014-04-02 08:53:10)

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,626

Re: Urgent -Discrete Math problems (Graph)

hi Stefy,

Didn't know that.  But I think I have a proof that the only other solutions have this form:

A-B-C   D-E-F  G  H  ie.  Two triangles and two isolated loops.  (1120 of these!) plus any isolated loops or disconnected points (64 of these).

If I cannot have loops then the only solution is the trivial one with no connects at all.  ?????

It would be easier if there were 9 vertices. 

Maybe 'similar' doesn't mean what I said.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

cathyli1109

Guest

Re: Urgent -Discrete Math problems (Graph)

Almost trivial 2:  Connect each point only to itself with a directed loop.  Both matrices have 1s on the leading diagonal and zeros elsewhere.

As opposed to a multigraph, a simple graph is an undirected graph that has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices.

The only thing I am able to think up about this problem is that the graph has to have exactly 8 edges.

I think the graph have exactly 8 edges also.
But there would be many different isomorphic graph then.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,626

Re: Urgent -Discrete Math problems (Graph)

such that adjacency matrix is similar to its incident matrix.

Sorry, cathyli1109, but we need to know what you mean by this.  Please explain what similar means here.

Perhaps you could provide an example with 3 vertices to show what this means.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: Urgent -Discrete Math problems (Graph)

Maybe 'similar' doesn't mean what I said.

Have you seen the whole post #4?

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,626

Re: Urgent -Discrete Math problems (Graph)

Hi Stefy,

I assume you mean this bit:

I have no idea how to do that without knowing P.  There's a lot of 8 by 8 possibilities. 

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: Urgent -Discrete Math problems (Graph)

Yes, but we can start by noting that the graph conatins exactly 8 edges.

Last edited by anonimnystefy (2014-04-03 05:49:22)

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,626

Re: Urgent -Discrete Math problems (Graph)

Yes, and the incident matrix has exactly two ones and 6 zeros in each column.

And the adjacency matrix is symmetric.

I think the adjacency matrix will also only have ones and zeros but I cannot yet prove this.

Which would mean that when 'P' multiplies the incident matrix it must only pick out at most 1 of the ones; the other being zero'd.

I wonder whether there is any worth in trying a simpler case first; eg.  4 vertices.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Bob

Administrator

Registered: 2010-06-20

Posts: 10,626

Re: Urgent -Discrete Math problems (Graph)

bobbym, Your post has disappeared so this makes no sense now. 

Yup!  And I've got L1, L2, L3 and L4 too.

If I construct Matrices I and A, any hints about how to find P so that I = P-¹ A P. 
(obviously it may not exist for a random case, but I've got a hot favourite.    )

Bob

Last edited by Bob (2014-04-03 06:32:04)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Urgent -Discrete Math problems (Graph)

bobbym, Your post has disappeared

I just wanted to put a subliminal image in your mind.

It is easy to find P. The process is called diagonalizing a matrix and is a rote procedure. My favorite thing in the world, a no brainer! But it may not exist!

For anonimnystefy's definition of similarity

Uh oh! That may not be as easy.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: Urgent -Discrete Math problems (Graph)

the incident matrix has exactly two ones and 6 zeros in each column.

Why is that?

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

eigenguy

Member

Registered: 2014-03-18

Posts: 78

Re: Urgent -Discrete Math problems (Graph)

It is easy to find P. The process is called diagonalizing a matrix and is a rote procedure. My favorite thing in the world, a no brainer! But it may not exist!

???

You should share your great secrets with the world, then!

Diagonalizing, and its related problem of finding eigenvalues and eigenvectors, is a major subject of research for Numerical mathematics. For 5 dimensions or higher, it can only be done by iterative methods.
Check out the Wikipedia page "Eigenvalue Algorithm" for more information.

For 2x2 and 3x3, my favorite method is to solve the determinant equation for the eigenvalues, then exploit the Cayley-Hamilton theorem to find the eigenvectors. If you have enough independent eigenvectors to span the space, then you can use them as the columns of the matrix P (but normalize them first, so that P[sup]-1[/sup] = P[sup]T[/sup], which isn't necessary but is a lot easier).

---

"Having thus refreshed ourselves in the oasis of a proof, we now turn again into the desert of definitions." - Bröcker & Jänich

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Urgent -Discrete Math problems (Graph)

You should share your great secrets with the world, then!

Why be abrasive about it? You could be wrong? I am a person too, with feelings. I hope that will not continue.

Tact is the art of making a point without making an enemy.

I share the methods everyday. They are not my methods nor are they great secrets.

Diagonalizing, and its related problem of finding eigenvalues and eigenvectors, is a major subject of research for Numerical mathematics.

I am well aware of that but it is possible to be a bit behind the times concerning what a CAS can do. For the size of the problem being discussed here and for certain B's it is quite possible.

If you still do not agree that the finding of eigenvalues and eigenvectors has well passed a 2 x 2 or 3 x 3 stage then post a large problem in Help Me and I will work on it.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

eigenguy

Member

Registered: 2014-03-18

Posts: 78

Re: Urgent -Discrete Math problems (Graph)

I apologize for being abrasive. I had not intended to be so. I respect the generosity and intelligence you've amply demonstrated in these forums.

But I am not at all behind the times concerning what a CAS can do. My remarks are entirely acurate. Diagonalization by finite means is not possible beyond 4x4 matrices - at least not without involving trancendental functions, (which even if you used, also require iterative means to calculate). This is not a "nobody has figured out how to do it yet", but rather has been proven to be a fundamental limitation.

That said, there are, and have long been, iterative means of finding eigenvalues and eigenvectors for any size of matrix. But this remains an active area of research as people attempt to find new ways that work faster, either in general, or for specific classes of matrices. Most of the algorithms listed on the Wikipedia page were created within the last 30 years, many within the last 10. And there are others that are not listed.

As for size of matrices, I suspect the record is held by Google's Page Rank algorithm, which finds eignenvalues for a matrix whose dimension is in the trillions now, I think (one for each page on the internet). Fortunately, this matrix is very sparse - almost all of its entries are 0, which makes the job a lot easier.

---

"Having thus refreshed ourselves in the oasis of a proof, we now turn again into the desert of definitions." - Bröcker & Jänich

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Urgent -Discrete Math problems (Graph)

But I am not at all behind the times concerning what a CAS can do.

I have just got the eigenvalues of an 8 x 8 in closed form.

My remarks are entirely acurate.

So you see it is not impossible.

Iterative methods have now been improved greatly. We can now get exact answers from them in many, many cases.

There is a good chance that the matrices involved here ( consisting of 1's and 0's ) might respond well also.

Fortunately, this matrix is very sparse - almost all of its entries are 0, which makes the job a lot easier.

So are all these matrices and they are only 8 x 8.

Here is one that fits bob's criteria:

Eigenvalues = {2, -1, I, -I, 0, 0, 0, 0}

Eigenvectors:

This one as I said may not be diagonalizable but that has nothing to do with being unable to compute it.

Most of the algorithms listed on the Wikipedia page were created within the last 30 years, many within the last 10.

Not good enough. Many CAS algorithms are secret.

Here is an amazing polynomial:

Roots are:

Of course Abel's magnificent theorem is not being violated but can we always tell when one of these has an exact solution or not by inspection? Obviously not just by inspecting the largest exponent.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

eigenguy

Member

Registered: 2014-03-18

Posts: 78

Re: Urgent -Discrete Math problems (Graph)

I never said it was impossible. What is impossible is a general procedure for size > 4. One that works for every matrix. There are always special cases where it is possible to find the exact eigenvalues and eigenvectors (for triangular matrices it is trivial, no matter what the size).

Most of the algorithms listed on the Wikipedia page were created within the last 30 years, many within the last 10.

Not good enough. Many CAS algorithms are secret.

And in what way does this somehow counter the point from which my quote was taken, which was that eigenvalue algorithms are an active field of research?

So if we can please move away from talking past each other, I would rather return to the actual problem here:

Having looked up the definition of Adjacency and Incidence matrices. I note that the adjacency matrix is symmetric. If the incidence matrix is similar to it, it must be symmetric as well. Each row in the incidence matrix is a vertex, and each column is an edge. So each column has exactly two 1s. If the matrix is symmetric, each row has only two 1s as well. This means that each vertex is connected to exactly two edges. As a result, every vertex and every edge must lie in simple loop. If the graph is connected, then it has to be simply one big loop of eight vertices connected by eight edges. There is only one such graph.

Edited to add: I see that only in problem 2 does it assume the graph is connected. This broadens the choices:
a loop of 8
a loop of 6 and a loop of 2
a loop of 5 and a loop of 3
two loops of 4
a loop of 4 and and two loops of 2
two loops of 3 and a loop of 2
4 loops of 2

Last edited by eigenguy (2014-04-03 12:54:28)

---

"Having thus refreshed ourselves in the oasis of a proof, we now turn again into the desert of definitions." - Bröcker & Jänich

ShivamS

Member

Registered: 2011-02-07

Posts: 3,648

Re: Urgent -Discrete Math problems (Graph)

Here at MIT we have a whole faculty working on (at least related to) eigenvalues algorithms (I even was a part of it for a few months but then changed my field of research).

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Urgent -Discrete Math problems (Graph)

So if we can please move away from talking past each other,

Please do not include me in that statement. It may be true for you, I have honestly answered all your concerns.

What is impossible is a general procedure for size > 4.

A general procedure? Just because a compass and straight edge method does not always work what does that mean? Are those the only methods? The fact is I provided evidence, I can not make you look at it.

And in what way does this somehow counter the point from which my quote was taken, which was that eigenvalue algorithms are an active field of research?

I never said it was not.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

eigenguy

Member

Registered: 2014-03-18

Posts: 78

Re: Urgent -Discrete Math problems (Graph)

Apparently we can't move away from talking past each other.

You took my original quotes out of context. I was pointing that out. Now, you've taken that out of context as well. We could continue this, but it is a waste of time.

---

"Having thus refreshed ourselves in the oasis of a proof, we now turn again into the desert of definitions." - Bröcker & Jänich

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Urgent -Discrete Math problems (Graph)

Nope, you started this when you ridiculed this:

It is easy to find P. The process is called diagonalizing a matrix and is a rote procedure.

Nothing has been taken out of context.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

ShivamS

Member

Registered: 2011-02-07

Posts: 3,648

Re: Urgent -Discrete Math problems (Graph)

What's to ridicule about diagonalizing a diagonalizable matrix? (sorry for intervening).

Last edited by ShivamS (2014-04-03 13:48:16)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Urgent -Discrete Math problems (Graph)

I do not know. I think it is easy to do even for those 8 x 8.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.