Linear Algebra Linear Algebra Math Forum

October 16th, 2018, 12:53 PM   #11
Senior Member

Joined: Sep 2016
From: USA

Posts: 684
Thanks: 459

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
 Originally Posted by zylo Ref preceding post. It doesn't work. You can't change induction premise by reordering. For example, suppose I have reordered to put $\displaystyle x_{2}$ in last place: $\displaystyle B(x,x) = x_{1}^{2}+ x_{3}^{2}+ x_{2}^{2}-x_{1}x_{3}-x_{3}x_{2}$ Now put $\displaystyle x_{2}$ back where it was $\displaystyle B(x,x) = x_{1}^{2}+ x_{2}^{2}+ x_{3}^{2}-x_{1}x_{2}-x_{2}x_{3}$ They aren't the same.
lmao October 16th, 2018, 05:16 PM   #12
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
 Originally Posted by zylo Ref preceding post. It doesn't work. You can't change induction premise by reordering.
True. Forget the reordering then - it was only to try and make the notation easier.

Suppose the result holds for some $n \geq 2$. Say $(x_1, \dots, x_{n+1}) \neq 0$ and suppose $x_j$ is maximal amongst the $x_i$. Consider the $n$-tuple $x = (x_1, \dots, \overline{x_j}, \dots, x_{n+1})$, where the overline indicates we are deleting the $j$-th entry. If $x = 0$ then we're fine: $\operatorname{LHS} = x_j^2 > 0 = \operatorname{RHS}$, so suppose $x \neq 0$. If $j = n+1$, then my old argument works. Else

$$\sum_{i=1}^{n+1} x_i^2 - \sum_{i=1}^{n}x_i x_{i+1} = \underbrace{\left(\sum_{\substack{i=1 \\ i \neq j}}^{n+1} x_i^2 - \sum_{\substack{i=1 \\ i \neq j}}^{n}x_i x_{i+1}\right)}_{>0 ~ \text{by inductive hypothesis applied to x}} + \underbrace{\left(x_{j}^2 - x_j x_{j+1}\right)}_{\geq 0 ~ \text{as} ~ x_j ~ \geq ~ x_{j+1}} > 0.$$ October 17th, 2018, 06:50 AM #13 Banned Camp   Joined: Mar 2015 From: New Jersey Posts: 1,720 Thanks: 126 Ref previous post. Same problem. $\displaystyle B(x,x)=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}-x_{1}x_{2}-x_{2}x_{3}$ $\displaystyle B(x,x)=x_{1}^{2}+x_{3}^{2}-x_{2}x_{3} +(x_{2}^{2}-x_{1}x_{2})$ But you need $\displaystyle x_{1}x_{3}$ for induction to work. I don't think you can use induction on size of a vector space. October 17th, 2018, 07:20 AM   #14
Senior Member

Joined: Sep 2016
From: USA

Posts: 684
Thanks: 459

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
 Originally Posted by cjem True. Forget the reordering then - it was only to try and make the notation easier.
Your argument was fine the first time. The induction assumption is that it holds for any collection of $n$ real numbers. If you now give me a collection of $n+1$, induction can be applied to any $n$-sized subset. Namely, you can assume the odd one out is the largest, smallest, or any other ordering you like. October 17th, 2018, 07:49 AM   #15
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
 Originally Posted by zylo Ref previous post. Same problem.
Apologies. Not really sure what I was thinking yesterday. For any $x = (x_1, \dots, x_n)$, we have

\begin{align*} B(x,x) &= 2 \sum_{i=1}^{n}x_{i}^2-2\sum_{i=1}^{n-1}x_{i}x_{i+1} \\ &= x_1^2 + x_n^2 + \sum_{i=1}^{n-1} (x_i^2 + x_{i+1}^2 - 2x_i x_{i+1}) \\ &= x_1^2 + x_n^2 + \sum_{i=1}^{n-1} (x_i - x_{i+1})^2 \\ &\geq 0 \end{align*}

Moreover, this shows $B(x,x) = 0$ if and only if $0 = x_1^2 = x_n^2 = (x_i-x_{i+1})^2$ for all $i = 1, \dots, n-1$. In other words, if and only if all the $x_i$ are equal to each other and $x_1 = x_n = 0$. But this is equivalent to $x = 0$.

Quote:
 Originally Posted by zylo I don't think you can use induction on size of a vector space.
You certainly can use induction on dimension to prove things about (finite-dimensional) vector spaces. It just didn't turn out to be helpful in this particular example, at least the way I was trying it. October 17th, 2018, 07:53 AM #16 Banned Camp   Joined: Mar 2015 From: New Jersey Posts: 1,720 Thanks: 126 B is a quadratic form which can be written as x'Ax which is positive definite if the eigenvalues of A are positive. EDIT: Discovered last post when I posted this. It is correct and nice- thanks. Do you have an example of induction on size of a vector space? Off-hand I can only think of induction in a vector space, like associativity. Last edited by zylo; October 17th, 2018 at 08:17 AM. October 17th, 2018, 08:03 AM   #17
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
 Originally Posted by SDK Your argument was fine the first time. The induction assumption is that it holds for any collection of $n$ real numbers. If you now give me a collection of $n+1$, induction can be applied to any $n$-sized subset. Namely, you can assume the odd one out is the largest, smallest, or any other ordering you like.
My first two attempts didn't work, for the reasons Zylo gave. While I certainly can apply induction to any subset of size $n$, that doesn't actually help.

e.g. say $x = (x_1, x_2, x_3)$ and say $x_2 \geq x_1, x_3$. I want to show that $x_1^2 + x_2^2 + x_3^2 - x_1 x_2 - x_2 x_3 > 0$.

Applying the inductive hypothesis to $(x_1, x_3)$ (assuming it's not $(0,0)$) tells me that $x_1^2 + x_3^2 - x_1 x_3 > 0$. But now I'm stuck with this $x_1 x_3$ term... I can still conclude $x_1^2 + x_2^2 + x_3^2 - x_1 x_3 - x_2 x_3 > 0$ and $x_1^2 + x_2^2 + x_3^2 - x_1 x_3 - x_1 x_2 > 0$, but neither of these facts are of any use.

Quote:
 Originally Posted by zylo Do you have an example of induction on size of a vector space? Off-hand I can only think of induction in a vector space, like associativity.
This is used all the time in field theory. For instance, if you look at any book on elementary Galois theory, you'll see plenty of examples.

Last edited by cjem; October 17th, 2018 at 08:37 AM. October 17th, 2018, 08:37 AM   #18
Banned Camp

Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 126

Quote:
 Originally Posted by zylo Do you have an example of induction on size of a vector space? Off-hand I can only think of induction in a vector space, like associativity.
Maybe you missed my last-minute edit. Just curious. October 17th, 2018, 08:54 AM   #19
Banned Camp

Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 126

Sorry I missed end of your last post.

Quote:
 Originally Posted by cjem This is used all the time in field theory. For instance, if you look at any book on elementary Galois theory, you'll see plenty of examples.
My question wasn't about field theory. You and SDK implied it was obvious for Vn. October 17th, 2018, 09:10 AM   #20
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
 Originally Posted by zylo My question wasn't about field theory.
Sure, but there are a lot of examples of what you want in field theory. Anyway, another option: proofs of Engel's and Lie's theorems (in the theory of Lie algebras). The standard proofs are quite explicitly done by induction on the dimension of vector spaces. Even if you don't understand all the details, the overall structure of the proof and the way induction is used should hopefully be clear.

Last edited by cjem; October 17th, 2018 at 09:19 AM. Tags product, show Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post srecko Linear Algebra 1 October 27th, 2016 12:25 PM X-Toxic Venomm New Users 1 December 27th, 2013 10:13 AM Schrodinger Complex Analysis 1 November 10th, 2011 02:55 PM notnaeem Real Analysis 4 August 16th, 2010 01:32 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      