I realize this is the Smith Normal Form and there is an algorithm in even the general case

just wondering if there were some snappier way to understand it

i guess this probably follows from basic Gaussian elimination arguments and understanding the matrices that give you the various reductions

my question is probably not very interesting, there probably is no deep way of looking at it

as always, thank you chat.stackexchange for letting me sound out my ideas into the abyss

don't underestimate sounding out ideas into the abyss... :)

yes, you are right @MarianoSuárezAlvarez

I don't have any insights into that, really

I think the existence of the Smith NS is quite extraordinary

it fails very badly for non-PIDs

i asked the question because it seems intimately related to the structure theorem

i wondered how easily you could "go backwards"

like if there were a nice reason you could diagonalize any jordan block, i think you would be done

it is equivalent to the structure theorem

more or less

@MarianoSuárezAlvarez, that would be a snappy way to understand it imo

how is it (more or less) equivalent?

compare the information provided by the structre theorem on a f.g. abelian group A

and the information provided by the Smith NF of the matrix A such that the cokernel of Z^n --> Z^m is A

(every f.g.abelian group is the cokernel of such a map)

i'm not sure i understand where $Z^n\to Z^m$ is coming from

let A be a f.g. abelian group

then it has a finite set of generators $\{a_1, \dots, a_m\}$

let $\phi:Z^m\to A$ be the map which maps $e_i, the $i$th vector of the standard basis, to $a_i$.

it is a surjection

let $\{b_1,\dots,b_n\}$ be a generating set of its kernel

repeat the game to get a map $\psi:Z^n\to\ker\phi$.

Now consider the composition $f:Z^n\to\ker\phi\hookrightarrow Z^m$. The cokernel of $f$ is isomorphic to $A$

ok, i understand this...how is this related to the smith normal form?

a key point being that eveyr subgroup of $Z^m$ (in particular, the kernel of $\phi$) is finitely generated

the map $f $ is given by multiplication by a matrix $M$

now pick an example and actually compute the SNF for the matrix M, and the decomposition of the group A given by the structure theorem

then look at the two, and try to see what the relation is

I will not tell you :)

if one example is not sufficiently good to see the relation, do another example

ok, thanks for the lead!

math.stackexchange.com/questions/131542/… rubs me the wrong way :/

@MarianoSuárezAlvarez, do you have a suggestion for a f.g. abelian group to consider. torsion groups seem trivial

do trivial examples

they will not hurt

i chose $A=Z/p\oplus Z/q$

do that one

so that the kernel is trivial, and $M$ is given by a diagonal matrix with $p$ and $q$ in the diagonal

er, with 1 in the diagonal

why is the kernel trivial?

it isn't...

oh, i'm being stupid

thanks

no map $Z^n\to Z/p\oplus Z/p$ has trivial kernel

i know, i'm sorry

i can be very obtuse

don; t be sorry

"sorry" does not apply to learning math

sorry applies to offences, and the like

you made a mistake

which is in a completely different ballpark

yes, you're right :)

so in this case the kernel is given by the 2x2 matrix with $p$ and $q$ along the diagonals. these are exactly what we are modding out by in the structure theorem. is that the idea?

yes

but try now to pick different generating sets

even redundant ones

and if i had a nontorsion part, the kernel would be trivial in that block

what do you mena redundant ones?

mean*

your choice of generating set reflects what the structure you know from the structure theorem

for example, consider the generating set $\{(2,1),(1,2),(3,5)\}$

(assuming $p$, $q>5$...)

You can even consider things like $\{(2,1),(4,2),(1,2),(2,4),(3,5),(4,7)\}$

so the point i guess is that given a matrix $A$ one can associate to it a finitely generated abelian group? and the diagonal is given by the structure theorem?

you picked a minimal generating set—mine are redundant in that they have too many elements, not "independent"

of course those are linearly dependent (the sets you gave), so we will get the same thing

I said I would not tell you

with more zeros

I'll keep my word

the kernel must be the same thing by the structure theorem!

the structure theorem does not say anything about the kernel

in fact, there is no mention of a kernel in the structure theorem!

in fact, when there are redundancies, the kernel is emphatically not the same

do an example and see!

ok ok

after doing a few examples, you will be able to exactly predict the smith normal norm of any matrix M such that its cokernel is isomorphic to A, starting from the information given by the structure theorem applied to A

and conversely

(notice that there is also a choice in the choice of generators for the kernel of the first map $Z^n\to A$, so for a given group A there are many many matrices M!)

i don't see the importance of the choice of the generating set of the image, only of the kernel, since the cokernel gives you everything as you've said

oh, nvm

notice that for example the size of the matrix depends on how many generators you pick for A and for the kernel of the map $Z^n \to A$

@MarianoSuárezAlvarez, do you agree that if $a,b,c$ are indeterminates, then $x^3+ax^2+bx+c$ is irreducible in $k[a,b,c][x]$, since we have the canonical isomorphism with $k[a,b,x][c]$ and this polynomial is just monic there, and thus irreducible trivially?

i will come back to our problem, i promise. i just can't tonight.

was making too many stupid mistakes and am getting tired, have to keep studying and not pursue interesting digressions. scout's honor i will complete the example ;)

there are others ways to do this problem via other canonical isomorphisms and Eisenstein's criterion, but this just seems like the easiest path

yes, regarding the polynomials

How can I see that $\{ x_1^{h_1}\cdots x_n^{h_n} : 0\le h_i\le n-i\}$ is a basis for $\Bbb Z[x_1,\cdots, x_n]$ over $\Bbb Z[e_1,\cdots, e_n]$, where $e_i$ are the elementary symmetric polynomials?

(above $\Bbb Z$ could actually be an arbitrary ring instead)

@TylerBailey Hey Tyler,i would appreciate it if you could upload the material in the concerned topic of 'developing reals from rationals with Cauchy sequences'.Thanks a ton!I needed this.

@anon, is that the fundamental theorem of symmetric polynomials?

@Antonio: That says $R[x_1,\cdots,x_N]^{S_n}\cong R[e_1,\cdots,e_n]$, which I already know and understood the proof of from my text. How do I see that the set I gave is a basis for $R[x_1,\cdots,x_n]$ over $R[e_1,\cdots,e_n]$?

@anon, "divide"

pick any polynomial, and show that you can write it as a linear combination with symmetric coefficients of those polynomials

order monomials lexicographically

start with a polynomial f

hm /me gotta run

yesterday @MarianoSuárezAlvarez helped me with a problem and the key to solving it was the following "lemma"/"obvious fact??" that if $R$ is a commutative ring of endomorphisms on a finite dimensional complex vector space $V$, then for $\lambda$ eigenvalue of some $r\in R$, $V_\lambda$ is invariant under $R$. and therefore all operators in $R$ share a common eigenvector...

but what if you have $S$ and $T$ two operators, and $V_\lambda$ a $2$ dimensional eigenspace for $T$ spanned by $\{v,w\}$, what if $S$ sends $v$ to $w$ and vice versa

then $V_\lambda$ is stabilized, but not invariant. and though you can find a stable eigenvector, $v+w$ for instance, it doesn't seem a priori clear that you can always find such a thing

but i know that it is. can someone help clear up my confusion?

i guess my confusion is that if $S$ and $T$ both have $\lambda$-eigenspaces, what if neither is strictly contained in the other

there "therefore" in your description of the argument is a bit longer than what the word might suggest...

Lemma. Let r and s be two commuting endomorphisms of a vector space V, and let $V_\lambda$ be the subspace of eigenvectors for $r$ for the eigenvalue $\lambda$. Then $s(V_\lambda)\subseteq V_\lambda$.

yes, i agree with this lemma and agree it's trivial

I prefer not to use the word trivial

everything is trivial once you know why it is trivial

so in my example $s$ can permute the basis of $V_\lambda$

fair enough, Mariano

I don't see what the problem is with your example

the matrices $\begin{pmatrix}2&0\\0&2\end{pmatrix}$ and $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ commute

and the vector space of eigenvectors for the first one is invariant under the second one

it is not true that the second one acts as the identity on the space of eigenvectors of the first one for the eigenvalue $2$

my question is this

but nowhere did anyone claim or use that :D

yesterday you said, if i understand correctly, that if $V_\lambda$ is the eigenspace for some operator $r_1\in R$, then we can take $r_2\in R$ and consider $r_2V_\lambda\subset V_\lambda$. if this containment were not actually an equality, we could look at $r_3$ and apply it to this new, smaller subspace

is that correct?

no, that is not what I said

I said the following:

thanks for suffering fools gladly, btw :P

let $V_\lambda$ be one of the eigenspaces of $r_1\in R$

then $V_\lambda$ is invariant under all of $R$, that is, for all $r\in R$ we have $r(V_\lambda)\subseteq V_\lambda$. (This is the content of the Lemma above)

and the complete proof was:

Let us prove by induction that a commutative algebra of endomorphisms of a non-zero vector space $V$ has a common eigenvector, by doing induction on $\dim V$. If $\dim V=1$ there is nothing to prove.

yes, i agree with the lemma. either one of them is $m<n$ one dimensional or we run out of guys in the ring

Suppose now that $\dim V>1$. If there is a proper non-zero subspace $W\subsetneq V$ which is invariant under $R$, then by the induction hypothesis we know that $R$ has a common eigenvector on $W$. But that vector is also a common eigenvector of $R$ in $V$, so we are done.

$\clubsuit$: So we are left with considering the case in which $V$ does not contain any non-zero proper $R$-invariant subspaces.

yes, with you so far

Pick any $r\in R$. Since $\dim V>1$, $r$ has an eigenvalue $\lambda$; let $W\subseteq V$ be the corresponding subspace of eigenvectors.

$W$ is not zero.

If it is a proper subspace of $V$, then our lemma tells us that it is in fact $R$-invariant

but this goes against our hypothesis $\clubsuit$

it follows that we must have $W=V$

this means that $r$ is in fact a multiple of the identity

this is the point i failed to grasp

can you explain this last sentence

if the space of $\lambda$-eigenvectors for $r$ is the whole space, then $r$ is $\lambda Id$.

because $r$ multiplies every element of $V$ by $\lambda$

just as $\lambda Id$ does

ah, of course

we thus conlcude that every element of $R$ is a multiple of the identity

then it is obvious that there is a common eigenvector

and thus everything is an eigenvector

because any non-zero vctor is a common eignevector

so if we were assuming that $R$ was a finite commutative ring or group of automorphisms for instance, we could thus conclude that there is a basis of simultaneous eigenvectors in a similar way

I did not make any assumptions on $R$

i know, i am adding additional ones

i agree with your proof now, i'm sorry i needed to hear it again

the argument I gave works for an arbitrary set of endomorphisms

it is not true that you can find a basis of simultaneous eigenvectors, without further hypotheses on $R$

and my argument is not helpful at all in finding bases

even if $R$ is a finite group of automorphisms of a finite dimensional space?

that is a further hypothesis :D

i think we should be able to modify your argument

yes, i know it is Mariano

if the field is the complex field, then it is true that a finite abelian group of automorphisms has a common eigenbasis

i think we can just say that not only must each eigenspace be stabilized, but it must be invariant under all elements of the group. and then extend your argument

if i'm not mistaken we can apply this to each eigenspace

the two statements are the same

"each eigenspace is stabilized"

and "it is invariant under all elements of the group"

i thought invariant would give us that $rV\lambda=V_\lambda$

rather than just containment

well: now you are talking about automorphisms

so they do mean the same thing in the context you chose

yes that's what i was trying to say

sorry for switching contexts so abruptly

the thing is, it is false that a finite abelian group of automorphisms of a finite dimensional vector space over an algebraically closed field has an eigenbasis

really?

for that to be true you need to assume, for example, that the field is of characteristic zero

it follows that at some point we need to use that information

ok, i see. i was thinking implicitly about a $C$ vector space

the argument we used to prove the existence of a common eigenvector does not care about the characteristic

in this case i would say that $V$ is the sum of the eigenspaces for any operator

and that any other automorphism has to preserve this sum's "structure"

that is not true

in this obvious way

oh, that's for diagonalizable only

shoot, you're right

in a finite group of automophisms of a complex vector space, every element is diagonalizable

yet it is rare that there is an eigenbasis for the whole group

indeed, that can only happen if the group is abelian

the group is abelian, but why would the automorphisms be diagonalizable in this case?

hm?

because they are of finite order

before going any further, you have to prove that a finite order automorphism of a finite dimensional complex vector space is diagonalizable

i guess if $S$ has order $n$ then $S^n-Id$ annihilates all vectors in $V$

so the $n$-th roots of unity are distinct eigenvectors?

is that sufficient, @MarianoSuárezAlvarez?

err

distinct eigenvalues

The multiplication by $-1$ on $\mathbb C^{1000}$ is a finite order endomorphism of that vector space which does not have distinct eigenvalues

rather the minimal polynomial should have distinct roots

yes, i'm just very tired

you should go to sleep if you are tired :)

the min. polynomial having distinct roots is equivalent to diagonalizability

i probably will sign off and head home after i understand this

and sleep!

so why are you asking if that is sufficient? :D

it is, indeed

sweet!

@MarianoSuárezAlvarez, thanks as ever for your graciousness, goodwill and insight

goodnight

haha

np

Hi @Mariano

hello, is there anyone who understands vectors? i really want to ask quick question for perpendicular unit vector

is that correct?

i assumed k = 0, so i could solve equation

wrong

why?

are you trying to solve?

i've spent 2 hours, it's 6am, i cant do it anymore...

why u removed?

never mind, i thoughtlessly typed upsomething

find a,b,c such that 4a+2b-3c = 0, now (ai+bj+ck)/sqrt(a^2+b^2+c^2) is the required one

to start with assume a = some 5 and b = some -4, now find c from above equation, you are done

@hey, a hint for finding a, b, and c: what is the lcm of 4, 2, and 3?

you get c = 4

now the answer is (5i-4j+4k)/sqrt(57)

remember there isn't a unique answer, it will depend on what you assume

@hey

Hey guys. I'm new here so I don't exactly know how this works. But I'll give it a shot by asking you: what is the proof to the fact that the dimension of vector space of all mxn matrices is mn?

Exhibit a basis of cardinality mn. The basis consists of matrices that are 1 in the i-th column j-th row and 0 elsewhere, running over all available i,j.

Hi @anon

Thanks @anon

Also, could somebody help me figure out something from this question math.stackexchange.com/a/131961/28259

I understand the first half of the answer, but I'm having trouble in the second half (namely from where it says "connection between the two" to the end). Can somebody try to break it down?

@NicoBellic Well what arturo is saying is that

linear transformations and matrices are not exactly the same thing

however picking a basis for the domain $V$ and codomain $W$

you can then identify a linear transformation with a matrix and vice versa.

hey @Raj

Say T:V->W. You're saying that there is a matrix that when multiplied by a vector in v in V will give a vector w in W?

In order to multiply a matrix by a vector, you need that vector to be in component form, i.e. you need a basis like {(1,0), (0,1)}

Right. Given that the matrix is some nxm matrix, you can multiply it by v in V that is mx1 vector to give some nx1 vector w in W. This is done instead of just doing the linear transformation?

The idea is that the matrix associated to a linear transformation depends on what basis you use for the spaces V and W.

The transformation itself is purely abstract, while we can think of the matrix as a concrete, but not necessarily unique, way to realize / write down the transformation.

But it essentially does the same thing...

Two different matrices can describe the same linear transformation. Two different linear transformations can have the same associated matrix.

anyone good with graph theory?

i am trying to understand how to implement a result from a paper

@Nico: Do you know LaTeX?

No.

Oh. Well can you go here and follow the very first instruction?

"Let $T:V\to W$ be linear. Then for $u\in V,~ [T(u)]_\gamma = [T]_\gamma^\beta [u]_\beta$."

I assume you have beta and gamma switched around on [T] after the = sign.

(Then again, it's been awhile since I've seen the notation, I might be wrong.)

Nope it's just like that.

And sorry for the primitive notations. I'm just not familiar with this kind of stuff.

Yeah, I know. Is the bookmarklet working I linked you to?

Yes it is.

The notation you wrote is right, but in the beta is at the bottom and gamma at top after the = sign

So beta is the ordered basis of V and gamma of W

Oh okay.

So as I said, I'm really confused as to what they mean by those notations, especially by [T(u)]_\gamma

$[T(u)]_\gamma$ means the vector $T(u)\in W$ put into component form (ie (a,b,...)) using $\gamma$ as a basis. Whereas $[T]_\beta^\gamma$ is the matrix associated to the linear transformation that takes vectors from $V$ in component form (using $\beta$ as a basis) and when multiplied becomes a vector that is to be interpreted as in component form in $W$ with basis $\gamma$.

Holy sh.... everything just fell into place.

Thanks so much anon.

One way to conceive of what's happening is to think of $T$ as some magical process occurs and we have access to the result - we're able to put the result in some kind of component form using a device called a basis with which we use to write vectors explicitly. The LHS of the = sign means we apply the process and then use our device to interpret the output, while [contd]

the RHS means we first apply our device to the input to write it in component form, and instead of applying the process we use another device called a matrix that allows us to simulate the effect of the transformation - we obtain an output that's already in component form and its the same as it would have been if we had gone the route of the LHS.

Such a simple concept now that you explained it. I've been struggling with this for 5+ hours. Thanks so much.

no problemo

@Mariano: Is having the username Administrator allowed?

I just saw that...

I'll ask

I hope not...

There are 2 persons and two bags of oranges present in system.A bag is assigned to person.Each bag contains some oranges in range 1-10.After opening each person has been asked if they want to trade or not if they both say yes then trading will happen,if they contradict they will get whatever present in their respective bags(no exchange).What is the maximum number of oranges for which either player says yes in a Nash equilibrium?

anyone can answer my question?

The setup isn't clear to me.

*their

assume they both say Yes and if person A has X oranges and person B has Y oranges then after trading person A will get Y oranges and person B will get X oranges

each person has bag that contains 1-10 oranges.After opening bag by each of them some third person will ask them if they want to exchange if they booth say yes then trading will happen if either of them says no then exchange will not happen and they will go home with whatever they have in thoer bag

Ello.

@MattN ello!

a duplicate

@tb hey

@MattN hey

I don't understand azarel's proof here: math.stackexchange.com/a/100928/5783

how did he get from $f(x_{n_k}) \rightarrow f(x)$ to $f(x_n) \rightarrow f(x)$??

Sorry was afk!

@BenjaminLim I don't understand what question azarel is answering.

@tb Closed. : )

Thanks!

@BenjaminLim Can't read this right now, I've got a major headache.

@BenjaminLim But if I understand the argument correctly, he shows that every subsequence has a further subsequence converging to $f(x)$, so the sequence itself must converge to $f(x)$. Suppose not...

woow, 10 minutes of thought?

: )

So I went to the French Language and Usage chat room to find out if Wikipedia's article's reference on the sign of zero being positive could be verified and this is the message that was left for me.

@tb How???

If we know that $f(x_n)$ is cauchy then ok

$f(x)$ must be the only limit point of $f(x_n)$.

(use compactness)

the only limit point of the set $f(x_n)$ you mean right?

@tb But theo I know that if a point $p$ is a limit point of a sequence say $p_n$

that does not mean that $p_n$ converges to $p$.

well, it does in presence of compactness

let me get rudin

no, just think!

: )

So theo we know that $f(x_{n_k})$ converges to $f(x)$

yes. Now suppose the sequence itself does not converge to $f(x)$. Then there is a subsequence that stays away from $f(x)$. By compactness...

ah ok

by compactness that subsequence has a further subsequence which converges to something else

say $p$

but then this means that this $p$ is a limit point of the set $f(x_n)$

yes I do mean $f(x_n)$

I am guessing from that the set $f(x_n)$ has only one limit point

I will have to prove that. @tb