Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 156 157 [158] 159 160 ... 173

Author Topic: Mathematics Help Thread  (Read 226928 times)

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2355 on: February 02, 2017, 01:27:18 pm »

So, going to ask this here though I know I probably won't get an answer.

Let A be a matrix over the finite field F2. We know that at any point where ran(An)=ran(An+1), then ran(An)=ran(Ak) for all n<=k. My question is that, for the smallest n such that the above condition is satisfied (that is, the first power of n such that the next power has the same rank), is applying A to that element repeatedly guaranteed to get us a group?
Since the number of matrices in F2d×d is finite, the powers of A are bound to repeat eventually, and as soon as that happens the sequence of powers of A becomes periodic. Suppose An = An+k, where k is the period. Then the set {An, ..., An+k-1} with standard matrix multiplication is a group isomorphic to the cyclic group with k elements. The identity element of this group is An+i where i is chosen such that n+i is divisible by k.
Logged

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2356 on: February 02, 2017, 02:16:10 pm »

Alright. Suppose n is the first positive power after which the nullity does not increase, and let's interpret the matrices as linear endomorphisms on F2n. Let M = An. We know that ker(M) = ker(M²) (<1>), since the first is a subset of the second, but they have equal dimension d - rank(M) = d - rank(M²).

Now let's prove that ker(M) is a complement of im(M) in F2n (<2>). Since they have dimension sum d, all we need to show is that they intersect trivially.
For this, Let x be any element in the intersection of ker(M) and im(M). Since x lies in im(M), there is an y such that My = x. Now M²y = Mx = 0, therefore y lies in ker(M²) and therefore by <1> also in ker(M), so x = My = 0.

Now let B = Amk+n, where m is chosen sufficiently high such that B lies in the aforementioned group, so B = AkB. We want to show that B = M (implying that M lies in the group). For this, using <2> all we need to do is show that B and M induce the same maps on both im(M) and ker(M). Clearly both B and M map all of ker(M) to 0, so it remains to show that Bx = Mx for all x in im(M).

By choice of B, AkB = Amk+n+k = Amk+n = B, so AkBx = Bx for all x, which means that Ak induces the identity map on im(B). We know that im(B) = im(M), since the first is a subset of the second, but both have the same dimension rank(M). Since Ak induces the identity on im(M), we get that Bx = MAmkx = Mx for all x in im(M). We're done!
« Last Edit: February 02, 2017, 02:21:00 pm by MagmaMcFry »
Logged

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2357 on: February 02, 2017, 04:49:41 pm »

First, the order of the group is k, not k-1. Second, An+i is not a generator of the group (it's the neutral element), but An+i+1 is.

Third, the maximum possible value of k is unfortunately exponential in d.

As a simple example, consider a permutation matrix. Since any permutation matrix is regular, the order of the induced group is equal to the order of the permutation, and the maximum permutation order is determined by Landau's function, which has subexponential behavior, but still grows faster than polynomially.

For a more complex example, suppose G is the finite field of order 2d. As all finite fields have cyclic multiplicative groups, we can take a generator c of this group and consider the G-linear map h : G -> G that takes any element in G and multiplies it by c. This map is G-linear, and the smallest k such that hk = idG is exactly k=2d-1 (the order of c in the multiplicative group).

Since F2 is a subfield of G, we can interpret G as a d-dimensional vector space over F2, which means that h is also F2-linear. Choose any basis of G as a F2-vector space, and let A be the transformation matrix of h with respect to this basis. Now A is a d×d matrix with values in F2, and by construction A has the same order as h.

So this second example proves that kmax(d) is bounded from below by 2d-1.
« Last Edit: February 02, 2017, 05:55:26 pm by MagmaMcFry »
Logged

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2358 on: February 03, 2017, 12:30:25 pm »

Hold up, you can't just assume that any noninvertible symmetric matrix satisfies the conditions of your problem.

Anyway, here's an easier way to count the number of symmetric matrices with A1 = 0. For any choice of all the values strictly below the diagonal, there's exactly one way to complete the matrix (first reflect the chosen values along the diagonal, then adjust the diagonal elements as prescribed. Since you may choose d(d-1)/2 matrix elements, there are 2d(d-1)/2 valid matrices.
Logged

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2359 on: February 03, 2017, 03:10:06 pm »

Nope. The matrix A = [[0,1,0],[1,0,0],[0,0,0]] is symmetrical, yet neither invertible nor nilpotent, but it does not satisfy your requirements, since A1 != 0.

Really, the matrices you need to consider are exactly those satisfying the linear equations A* = A and A1 = 0.

EDIT:
Quote
He proved that the maximum path of this "game of light" as he calls it on an arbitrary graph is equal to the order of that group
What exactly do you mean by "path"?

« Last Edit: February 03, 2017, 03:12:18 pm by MagmaMcFry »
Logged

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2360 on: February 03, 2017, 03:27:34 pm »

Oh okay, I see. So if I understand correctly, this is the (formalized) statement:

Suppose a matrix A in F2d×d satisfies A* = A and A1 = 0. Then there is an x in F2d such that the eventual period of (An) is the same as the eventual period of (Anx).
Logged

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2361 on: February 03, 2017, 03:40:13 pm »

Are you sure about that formulation? I believe you messed up your quantors there.
Logged

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2362 on: February 03, 2017, 05:00:41 pm »

I assume n is supposed to be greater than m. Anyway, we've proved that earlier.

Since we're in a finite-dimensional vector space, the following holds: [(For every x in F2d: Amx=Anx) <=> (Am = An)].
Since {A^m, ..., A^m+k-1} is the cyclic group we've been talking about all the time, and Am+k = Am, simply choose n = m+k.

Logged

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2363 on: February 04, 2017, 08:04:34 am »

I wrote a quick app that draws graphs and calculates their maximum period, and with a bit of playing around I found out that most cycle graphs Cp of prime length p have cycle length k = 2(p-1)/2 - 1, which is very exponential in nature. Notable exception is p = 17, where C17 has cycle length 15.
« Last Edit: February 04, 2017, 08:15:17 am by MagmaMcFry »
Logged

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2364 on: February 04, 2017, 08:45:35 am »

Okay, so I invented a way to transform an arbitrary directed graph with d vertices into a simple graph with O(d²)O(d) vertices that has at least the same light game period. Also I found a very simple infinite class of simple graphs with light game period Ω(2d/10) Ω(2d/3) Ω(2d/2), together with starting configurations that produce this period. Your professor might want to know about this.

E: Wait no I found a mistake. Brb

E2: Fixed my mistake and made the construction even better. Improved the constructed simple graph to size O(d) now!
« Last Edit: February 04, 2017, 11:07:02 am by MagmaMcFry »
Logged

TheBiggerFish

  • Bay Watcher
  • Somewhere around here.
    • View Profile
Re: Mathematics Help Thread
« Reply #2365 on: February 04, 2017, 11:39:39 am »

...Guys?  What on earth is this?
Logged
Sigtext

It has been determined that Trump is an average unladen swallow travelling northbound at his maximum sustainable speed of -3 Obama-cubits per second in the middle of a class 3 hurricane.

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2366 on: February 04, 2017, 12:07:26 pm »

This is the subtle science and exact art of mathematics. As there is little foolish calculator-waving here, many of you will hardly believe this isn't magic.
Logged

MagmaMcFry

  • Bay Watcher
  • [EXISTS]
    • View Profile
Re: Mathematics Help Thread
« Reply #2367 on: February 04, 2017, 02:04:22 pm »

Earlier on, I proved that the highest order of any cycle induced by a directed graph grows exponentially in the size of the graph. Now I found a method to convert any directed graph into a simple graph of proportional size that preserves the directed graph's loop structure, which means that the highest order of any cycle induced by simple graphs also grows exponentially in the size of the graph.

In other words, for any matrix A in F2d×d I've found a matrix B in F2O(d)×O(d) with B* = B and 1B = 0 and a mapping f : F2d -> F2O(d) such that for each x in F2d the eventual period of Bnf(x) is equal to the eventual period of Anx.
Logged

TheBiggerFish

  • Bay Watcher
  • Somewhere around here.
    • View Profile
Re: Mathematics Help Thread
« Reply #2368 on: February 04, 2017, 02:15:33 pm »

Are you, like, professional mathematicians or something?
Logged
Sigtext

It has been determined that Trump is an average unladen swallow travelling northbound at his maximum sustainable speed of -3 Obama-cubits per second in the middle of a class 3 hurricane.

Helgoland

  • Bay Watcher
  • No man is an island.
    • View Profile
Re: Mathematics Help Thread
« Reply #2369 on: February 04, 2017, 04:02:03 pm »

There's quite a few of us here actually. So far I haven't met another topologist though :/


For future reference: Is anyone here good with Category Theory and/or Set Theory?
Logged
The Bay12 postcard club
Arguably he's already a progressive, just one in the style of an enlightened Kaiser.
I'm going to do the smart thing here and disengage. This isn't a hill I paticularly care to die on.
Pages: 1 ... 156 157 [158] 159 160 ... 173