Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Helgoland]

Good as in 'better than me'. I'm trying to figure out whether I can turn to this thread for help if I encounter trouble with my studies.

[MagmaMcFry]

I'm not entirely sure that's possible. If so, give me the simple graph with the same loop structure as this directed graph:

Spoiler (click to show/hide)

Ideally a simple graph that can be extended to match that directed graph if extended to an infinite length.

Okay, so here's the algebraic idea: Suppose you have any matrix A corresponding to any directed graph with d vertices. Then B = [0,A,A ; A*,A*+A,A ; A*,A*,0] satisfies B = B* and B1 = 0, so B corresponds to a simple, even graph with 3d vertices, and for any state x of A, B[x;x;0] = [Ax;Ax;0], so [x;x;0] is a corresponding state of B with the exact same period as the state x of A.

Here's the geometric correspondence to this construction:

Spoiler (click to show/hide)

Each vertex becomes three vertices, and the edges are transformed as in the image. Clearly the resulting graph is simple and even. To transform any activation state, take each active circle and activate the corresponding square and diamond (not the triangle!). You'll see that a square is active iff its diamond is active, even after ticks, and that the triangles never activate, and that the left construction acts like a proper one-way gate.

Since all triangles are always off, we can just ignore them, and we get the following construction (straightening out the middle transformation):

Spoiler (click to show/hide)

Now this should make the relationship way clearer. But hold up, we have an issue now, since the graph is no longer even. To fix that, we can simply add a single triangle vertex, and connect it to every other vertex of odd degree. Since a diamond is connected to the triangle exactly when the corresponding square is connected to the triangle, the triangle will never become active and everything works out fine.

So here's the graph you asked for:

Spoiler (click to show/hide)

Of course, you can also directly reduce the size of the algebraic construction: B' = [0,A,A1 ; A*,A*+A,A1 ; 1A*,1A*,0] has size 2d+1, and we still have B' = B'* and B'1 = 0, and x still corresponds to [x;x;0], where the 0 is now a scalar instead of a vector.

Feel free to give me credit!

[hops]

How do I integrate (3x^2+7x+6)/(x^2+x+1)? I've been racking my brains and trying different combinations of partial fraction decomposition, integration by parts, etc. but I can't find a way to integrate it fully.

[TheDarkStar]

How do I integrate (3x^2+7x+6)/(x^2+x+1)? I've been racking my brains and trying different combinations of partial fraction decomposition, integration by parts, etc. but I can't find a way to integrate it fully.

Try polynomial long division; it should simplify stuff a bit. If that doesn't work, try completing the square somewhere.

[hops]

x^2+x+1 is unfactorable. I did long division, I still can't integrate (4x+3)/(x^2+x+1). I tried splitting it up. I still can't integrate 1/(x^2+x+1).

EDIT: Tried completing the square, the roots are imaginary.

[hops]

Nevermind, it would appear that I can still integrate it by decomposing it into complex fractions.

[frostshotgg]

It's integrable without decomposing into complex bullshit but it's almost unreasonably messy, because the way the denominator is lets you use a dirty version of the arctan integral. You wind up doing some integration by parts with it and get some variant of ln(x^2 + x + 1) + 1/(3^1/2) * arctan((2x+1)/(3^1/2) for each term.

Either way, it's very poorly behaved and probably outside the scope of your course. I would ask your instructor if they wanted you to just put "Not integrable" for it and move on.

[MagmaMcFry]

Choose a Galois field graph from the second example of this post. This d-vertex graph has a period of 2^d-1, applying the geometrical construction will give you a simple even graph with d' = 2d+1 vertices and a period of at least 2^d-1 = Ω(2^d'/2).

[MagmaMcFry]

I don't think looking at a graph will give you any more insights than what I already typed. Which part are you having trouble with? The Galois field construction, or the directed-to-simple transformation?

[hops]

isn't this technically computer science

[hops]

Huh. I thought data structures are solidly computer science's domain.

[Arx]

It's probably more a case of something that seems like Comp Sci actually being maths when you get right down to it. It's basically all graph theory, on some level.

[MagmaMcFry]

Galois field construction.

In that case looking at the graph will definitely not help you, since the adjacency matrix was constructed entirely by algebraic and non-graph-theoretical means. The matrix that is constructed has a really high period because it is a representation of a linear map that also has a really high period. I suggest you try to understand the algebraic construction instead.

[MagmaMcFry]

Second half? So the transformation method, not the Galois field construction? Okay, here's another more varied example graph together with its transformation.

Spoiler (click to show/hide)

The edge colors help match single edges in the source graph to their corresponding edges in the destination graph.

Again though, I'd recommend you understand the algebraic construction first, because it's conceptually way simpler.

Okay, so here's the algebraic idea: Suppose you have any matrix A corresponding to any directed graph with d vertices. Then B = [0,A,A ; A*,A*+A,A ; A*,A*,0] satisfies B = B* and B1 = 0, so B corresponds to a simple, even graph with 3d vertices, and for any state x of A, B[x;x;0] = [Ax;Ax;0], so [x;x;0] is a corresponding state of B with the exact same period as the state x of A.

[TheBiggerFish]

@Cinder:No, data structures are mathy, CS people just abuse them for fun and profit.