Print

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

[MagmaMcFry]

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 F₂. We know that at any point where ran(Aⁿ)=ran(Aⁿ⁺¹), then ran(Aⁿ)=ran(A^k) 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 F₂^d×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 Aⁿ = A^n+k, where k is the period. Then the set {Aⁿ, ..., A^n+k-1} with standard matrix multiplication is a group isomorphic to the cyclic group with k elements. The identity element of this group is Aⁿ⁺ⁱ where i is chosen such that n+i is divisible by k.

[MagmaMcFry]

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 F₂ⁿ. Let M = Aⁿ. 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 F₂ⁿ (<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 = A^mk+n, where m is chosen sufficiently high such that B lies in the aforementioned group, so B = A^kB. 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, A^kB = A^mk+n+k = A^mk+n = B, so A^kBx = Bx for all x, which means that A^k 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 A^k induces the identity on im(M), we get that Bx = MA^mkx = Mx for all x in im(M). We're done!

[MagmaMcFry]

First, the order of the group is k, not k-1. Second, Aⁿ⁺ⁱ is not a generator of the group (it's the neutral element), but Aⁿ⁺ⁱ⁺¹ 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 2^d. 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 h^k = id_G is exactly k=2^d-1 (the order of c in the multiplicative group).

Since F₂ is a subfield of G, we can interpret G as a d-dimensional vector space over F₂, which means that h is also F₂-linear. Choose any basis of G as a F₂-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 F₂, and by construction A has the same order as h.

So this second example proves that k_max(d) is bounded from below by 2^d-1.

[MagmaMcFry]

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 2^d(d-1)/2 valid matrices.

[MagmaMcFry]

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:

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"?

[MagmaMcFry]

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

Suppose a matrix A in F₂^d×d satisfies A* = A and A1 = 0. Then there is an x in F₂^d such that the eventual period of (Aⁿ) is the same as the eventual period of (Aⁿx).

[MagmaMcFry]

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

[MagmaMcFry]

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 F₂^d: A^mx=Aⁿx) <=> (A^m = Aⁿ)].
Since {A^m, ..., A^m+k-1} is the cyclic group we've been talking about all the time, and A^m+k = A^m, simply choose n = m+k.

[MagmaMcFry]

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 C_p 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 C₁₇ has cycle length 15.

[MagmaMcFry]

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 Ω(2^d/10) Ω(2^d/3) Ω(2^d/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!

[TheBiggerFish]

...Guys?  What on earth is this?

[MagmaMcFry]

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.

[MagmaMcFry]

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 F₂^d×d I've found a matrix B in F₂^O(d)×O(d) with B* = B and 1B = 0 and a mapping f : F₂^d -> F₂^O(d) such that for each x in F₂^d the eventual period of Bⁿf(x) is equal to the eventual period of Aⁿx.

[TheBiggerFish]

Are you, like, professional mathematicians or something?

[Helgoland]

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?