Integral Basis...

Mar 2009
76
2
Suppose I have a basis A=(a1,a2,...,an) for the nullspace of a matrix with integer coefficients (i.e. Q-linear combinations of A will give me the span of A). I want to find the integral basis for this (perhaps my terminology isn't correct... but what I mean is I want to find a basis B=(b1,b2,...,bn) where the bi's are integers, such that Z-linear combinations of B will give me the span of the A.)

I'm not sure how to do this. In algebra class, given a field Q(sqrt(d)) I remember finding integral basis' for this... but I can't figure out whether what I'm doing here is at all similar... or much easier... any suggestions would be appreciated!
 

chiro

MHF Helper
Sep 2012
6,608
1,263
Australia
Hey gummy_ratz.

Will the basis of A span A and thus give you a basis such that all linear combinations of those vector span the set A? If you have a full-rank system, then the basis should provide you with your basis b.
 

Deveno

MHF Hall of Honor
Mar 2011
3,546
1,566
Tejas
suppose A = {a1,...,an} is a basis for a vector space V.

suppose further that k ≠ 0 in the field F that V is a vector space over.

is B = {ka1,...,kan} also a basis? let's see:

suppose c1(ka1) +...+ cn(kan) = 0.

then k(c1a1 +...+ cnan) = 0.

since k ≠ 0, c1a1 +...+ cnan = 0.

by the linear independence of the aj, c1 =...= cn = 0.

thus the kaj are also linearly independent.

we know that the aj span V. this means given ANY v in V we can write:

v = c1a1 +...+ cnan for some cj in F.

thus v = (c1 /k)(ka1) +....+ (cn/k)(kan), so the kaj span V as well.

now, suppose that each aj = pj/qj, where the p's and q's are relatively prime integers for each j.

what about k = lcm(q1,..,qn)? this certainly gives a basis that is all integers.

however, i don't believe you can realize the span of this basis as Z-linear combinations, only as Q-linear combinations.

let me give an example:

suppose we have the matrix:

\(\displaystyle A = \begin{bmatrix}2&1&3\\4&-5&1\\6&-4&4 \end{bmatrix} \)

which has a null space with basis {(8,5,-7)}. now (1,5/8,-7/8) is also in this null space, but NO Z-multiple of (8,5,-7) will ever give us (1,5/8,-7/8).
 
Mar 2009
76
2
Hi Deveno,

What I'm looking for is not a basis with integer coefficients that spans the same space as the null space of A... But I want a basis with integer coefficients that hits every vector with integer coefficients in the nullspace of A, i.e. null(A)nZ.

I know that given a basis for my nullspace, I can easily find a basis with integer coefficients by multiplying by a scalar k (e.g. the least common multiple of the the denominators of my generators), but is there a way to make sure that I'm hitting everything in null(A)nZ (the elements in the null space of A which have integer coefficients)?

So in your example, I'm not hoping to hit (1,5/8,-7/8) because it has rational coefficients... but I want to make sure I hit every vector with integer coefficients... (For example, suppose I chose (16, 10, -14) for my basis. Q-linear combinations will give me the span of null(A), but Z-linear combinations will not give me (8,5,-7) ).