Linear Algebra Marathon & Questions (1 Viewer)

seanieg89 · Oct 19, 2016

Linear Algebra Marathon & Questions
This is a marathon thread for linear algebra. Please aim to pitch your questions for first-year/second-year university level maths. Excelling & gifted/talented secondary school students are also invited to contribute.

(mod edit 7/6/17 by dan964)
===============================
To accompany the corresponding calculus thread.

First question (spectral theorem, familiarity with dot product recommended):

$Consider the vector space $\mathbb{K}^n$, where $\mathbb{K}$ is either $\mathbb{C}$ or $\mathbb{R}$ (fixed throughout the question).\\ \\If $A$ is a $n\times n$ matrix with entries in $\mathbb{K$}, we define the adjoint $A^*$ of $A$ by the identity $Ax\cdot y=x\cdot A^* y$ for all $x,y\in \mathbb{K}^n$, where the dot product is defined by\\ \\ $x\cdot y:= \sum_{j=1}^n x_j \bar{y}_j.$\\ \\We say that $A$ is Hermitian if it is equal to its own adjoint, and we say that $A$ is normal if it commutes with its own adjoint.\\ \\ 1. By considering the function $F(x):=Ax\cdot x$ on the unit sphere $S:=\{x:x\cdot x =1\}$, show that every Hermitian matrix possesses at least one eigenvector. Hint: The extreme value theorem implies that any continuous real-valued function on $S$ attains a maximum and a minimum...\\ \\ 2. Hence, prove that $\mathbb{K}^n$ has an orthonormal basis of eigenvectors of $A$, if $A$ is Hermitian.$

$\noindent 3. Deduce that the conclusion in 2. must also hold true for normal matrices $A$.$

InteGrand · Oct 29, 2016

Re: First Year Linear Algebra Marathon

$\noindent Let $A$ be a square matrix over $\mathbb{C}$ and suppose its eigenvalues are precisely its diagonal elements. Must $A$ be triangular? (Justify your answer.)$

leehuan · Nov 15, 2016

Re: First Year Linear Algebra Marathon

InteGrand said:
$\noindent Let $A$ be a square matrix over $\mathbb{C}$ and suppose its eigenvalues are precisely its diagonal elements. Must $A$ be triangular? (Justify your answer.)$

$\text{Counterexample: }\begin{pmatrix}0&1&0\\0&0&0\\0&1&0\end{pmatrix}$

dan964 · Nov 16, 2016

Re: First Year Linear Algebra Marathon

A nice and simple question for first year uni students:
Prove the Cauchy-Schwarz inequality.

Paradoxica · Nov 16, 2016

Re: First Year Linear Algebra Marathon

dan964 said:
A nice and simple question for first year uni students:
Prove the Cauchy-Schwarz inequality.

This is not a first year level problem...

unless you're asking for the vector form of the inequality.

For the sum form of the inequality, the proof is trivial.

Consider the following quadratic equation in x:

$\noindent$ \sum_{k=1}^n (a_k x - b_k)^2 \ge 0 \\\\ \left(\sum_{k=1}^n a_k^2 \right)x^2 - 2 \left(\sum_{k=1}^n a_k b_k \right)x + \left(\sum_{k=1}^n b_k^2 \right) \ge 0 \\\\ $It is obvious that the discriminant of the equation is non-positive.$ \\\\ 4 \left(\sum_{k=1}^n a_k b_k \right)^2 - 4\left(\sum_{k=1}^n a_k^2 \right)\left(\sum_{k=1}^n b_k^2 \right) \le 0 \\\\ $Which rearranges into the desired inequality by inspection. Equality happens if and only if all of the $a_k$ are equal to each other, and all of the $b_k$ are equal to each other.$

In future, you should not omit detail, unless the context makes it clear. Which for this one, probably means vector form.

dan964 · Nov 16, 2016

Re: First Year Linear Algebra Marathon

Paradoxica said:
This is not a first year level problem...

unless you're asking for the vector form of the inequality.

For the sum form of the inequality, the proof is trivial.

Consider the following quadratic equation in x:

$\noindent$ \sum_{k=1}^n (a_k x - b_k)^2 \ge 0 \\\\ \left(\sum_{k=1}^n a_k^2 \right)x^2 - 2 \left(\sum_{k=1}^n a_k b_k \right)x + \left(\sum_{k=1}^n b_k^2 \right) \ge 0 \\\\ $It is obvious that the discriminant of the equation is non-positive.$ \\\\ 4 \left(\sum_{k=1}^n a_k b_k \right)^2 - 4\left(\sum_{k=1}^n a_k^2 \right)\left(\sum_{k=1}^n b_k^2 \right) \le 0 \\\\ $Which rearranges into the desired inequality by inspection. Equality happens if and only if all of the $a_k$ are equal to each other, and all of the $b_k$ are equal to each other.$

In future, you should not omit detail, unless the context makes it clear. Which for this one, probably means vector form.

Yes I was asking for inner product spaces, that is for vectors.

leehuan · Nov 16, 2016

Re: First Year Linear Algebra Marathon

$\text{They showed one of the many proofs of it in my lecture last sem.}$

$\begin{align*}p(\lambda)&=|\textbf{a}-\lambda\textbf{b}|^2\\ &=(\textbf{a}-\lambda\textbf{b})\cdot \textbf{a}-\lambda\textbf{b}\\ &= |\textbf{a}|^2-2\lambda \textbf{a}\cdot\textbf{b}+\lambda^2 |\textbf{b}|^2 \end{align*}\\ \text{And note that }p(\lambda)\ge 0$

$\\ \text{From 2U methods, we see that }p\text{ is miniimised when }\lambda = \frac{\textbf{a}\cdot\textbf{b}}{|\textbf{b}|^2}\\ \text{Substituting back in gives }\min_{\lambda \in \mathbb R}p(\lambda)=|\textbf{a}|^2-\frac{(\textbf{a}\cdot \textbf{b})^2}{|\textbf{b}|^2}$

$\\\text{So from }p(\lambda )\ge 0\text{ and }|\textbf{x}|\ge 0\\ \text{Rearranging gives }|\textbf{a}\cdot \textbf{b}|\le |\textbf{a}||\textbf{b}|$

Paradoxica said:
unless you're asking for the vector form of the inequality.

I did not even know that there was a sum form until doing past papers for 1251. Then I had to figure out why the sum and vector forms were equivalent.

Paradoxica · Nov 16, 2016

Re: First Year Linear Algebra Marathon

leehuan said:
$\text{They showed one of the many proofs of it in my lecture last sem.}$

$\begin{align*}p(\lambda)&=|\textbf{a}-\lambda\textbf{b}|^2\\ &=(\textbf{a}-\lambda\textbf{b})\cdot \textbf{a}-\lambda\textbf{b}\\ &= |\textbf{a}|^2-2\lambda \textbf{a}\cdot\textbf{b}+\lambda^2 |\textbf{b}|^2 \end{align*}\\ \text{And note that }p(\lambda)\ge 0$

$\\ \text{From 2U methods, we see that }p\text{ is maximised when }\lambda = \frac{\textbf{a}\cdot\textbf{b}}{|\textbf{b}|^2}\\ \text{Substituting back in gives }\max_{\lambda \in \mathbb R}p(\lambda)=|\textbf{a}|^2-\frac{(\textbf{a}\cdot \textbf{b})^2}{|\textbf{b}|^2}$

$\\\text{So from }p(\lambda )\ge 0\text{ and }|\textbf{x}|\ge 0\\ \text{Rearranging gives }|\textbf{a}\cdot \textbf{b}|\le |\textbf{a}||\textbf{b}|$

I did not even know that there was a sum form until doing past papers for 1251. Then I had to figure out why the sum and vector forms were equivalent.

olympiad kids be like that's the second thing I would have thought of...

first is power mean inequality, no less.

leehuan · Nov 16, 2016

Re: First Year Linear Algebra Marathon

Paradoxica said:
olympiad kids be like that's the second thing I would have thought of...

first is power mean inequality, no less.

Pretty sure this question is too elementary for olympiad level

seanieg89 · Nov 16, 2016

Re: First Year Linear Algebra Marathon

leehuan said:
$\text{They showed one of the many proofs of it in my lecture last sem.}$

$\begin{align*}p(\lambda)&=|\textbf{a}-\lambda\textbf{b}|^2\\ &=(\textbf{a}-\lambda\textbf{b})\cdot \textbf{a}-\lambda\textbf{b}\\ &= |\textbf{a}|^2-2\lambda \textbf{a}\cdot\textbf{b}+\lambda^2 |\textbf{b}|^2 \end{align*}\\ \text{And note that }p(\lambda)\ge 0$

$\\ \text{From 2U methods, we see that }p\text{ is maximised when }\lambda = \frac{\textbf{a}\cdot\textbf{b}}{|\textbf{b}|^2}\\ \text{Substituting back in gives }\max_{\lambda \in \mathbb R}p(\lambda)=|\textbf{a}|^2-\frac{(\textbf{a}\cdot \textbf{b})^2}{|\textbf{b}|^2}$

$\\\text{So from }p(\lambda )\ge 0\text{ and }|\textbf{x}|\ge 0\\ \text{Rearranging gives }|\textbf{a}\cdot \textbf{b}|\le |\textbf{a}||\textbf{b}|$

I did not even know that there was a sum form until doing past papers for 1251. Then I had to figure out why the sum and vector forms were equivalent.

Pretty sure you mean min. Also note that it looks mildly messier for complex inner product spaces but the same argument still works. (replace your 2a.b with $\langle a,b\rangle+\langle b,a\rangle$ ).

seanieg89 · Nov 16, 2016

Re: First Year Linear Algebra Marathon

$Let $A$ be an $n\times n$ matrix with coefficients in an arbitrary field $\mathbb{K}$. Explain why $V:=\textrm{Span}(I,A,A^2,A^3,\ldots)$ is a finite dimensional vector space. What is the maximal dimension of $V$? Rigorously justify your answer.$

seanieg89 · Nov 16, 2016

Re: First Year Linear Algebra Marathon

$Let $V$ be an arbitrary complex vector space equipped with a norm $\|\cdot\|$. Prove that there exists an inner product on $V$ such that $\langle x ,x \rangle=\|x\|^2$ for all $x\in V$ if and only if the norm satisfies\\ \\ $\|x+y\|^2+\|x-y\|^2=2(\|x\|^2+\|y\|^2)$\\ \\ for all $x,y\in V$.$

seanieg89 · Nov 16, 2016

Re: First Year Linear Algebra Marathon

$One more for good measure. Suppose $\|\cdot\|_1, \|\cdot\|_2$ are norms on a finite dimensional complex vector space $V$. Prove that there exist positive constants $A,B$ such that $A\|x\|_1\leq \|x\|_2\leq B\|x\|_1$ for all $x\in V$.\\ Prove that the same is not necessarily true if $\dim(V)=\infty$.$

(This result gives the first glimpse of why analysis of infinite dimensional vector spaces is far more subtle than that on finite dimensional vector spaces. A sequence can converge with respect to one norm but not with respect to another.)

InteGrand · Nov 16, 2016

Re: First Year Linear Algebra Marathon

If you managed to prove the Cayley-Hamilton theorem for complex matrices using a property of complex matrices (like that diagonalisable complex matrices form a dense set), would this automatically also imply the theorem for any field (or commutative ring), because the theorem is basically a bunch of algebraic identities that hold for any given matrix, and multiplication and addition etc. will all behave the same way regardless of what field the entries of the matrix come from?

seanieg89 · Nov 16, 2016

Re: First Year Linear Algebra Marathon

InteGrand said:
If you managed to prove the Cayley-Hamilton theorem for complex matrices using a property of complex matrices (like that diagonalisable complex matrices form a dense set), would this automatically also imply the theorem for any field (or commutative ring), because the theorem is basically a bunch of algebraic identities that hold for any given matrix, and multiplication and addition etc. will all behave the same way regardless of what field the entries of the matrix come from?

Would probably depend on exactly how you proved it. Most proofs would be valid for arbitrary fields, but if you did it using some very special facts about C, I don't know if it is any easier to pass from Cayley Hamilton for C to Cayley Hamilton for F than it is to just prove Cayley Hamilton for F from scratch.

InteGrand · Nov 16, 2016

Re: First Year Linear Algebra Marathon

seanieg89 said:
Would probably depend on exactly how you proved it. Most proofs would be valid for arbitrary fields, but if you did it using some very special facts about C, I don't know if it is any easier to pass from Cayley Hamilton for C to Cayley Hamilton for F than it is to just prove Cayley Hamilton for F from scratch.

$\noindent Like, if you know it for $\mathbb{C}$, would you need much real work to get to arbitrary $\mathbb{F}$? If $A = (a_{ij})$ and the $a_{ij}$ are arbitrary complex numbers, and we assume the Cayley-Hamilton Theorem for $\mathbb{C}$, isn't the theorem basically telling us that the expressions we get for $n^{2}$ entries of $\chi_{A}(A)$ (where $\chi_{A}(z)$ is the characteristic polynomial of $A$) are each going to end up cancelling to $0$? But the algebraic expressions we get for these $n^{2}$ entries in terms of $a_{11}$ up to $a_{nn}$ would be the same regardless of whether the $a_{ij}$ were complex or from an arbitrary field, and so if they all cancel out to $0$ for complex entries, they should do so for arbitrary field entries too, since the laws of arithmetic are all the same?$

Drsoccerball · Nov 16, 2016

Re: First Year Linear Algebra Marathon

Ill take a good look at this thread along with the advanced marthons while im overseas goodluck people

seanieg89 · Nov 16, 2016

Re: First Year Linear Algebra Marathon

InteGrand said:
$\noindent Like, if you know it for $\mathbb{C}$, would you need much real work to get to arbitrary $\mathbb{F}$? If $A = (a_{ij})$ and the $a_{ij}$ are arbitrary complex numbers, and we assume the Cayley-Hamilton Theorem for $\mathbb{C}$, isn't the theorem basically telling us that the expressions we get for $n^{2}$ entries of $\chi_{A}(A)$ (where $\chi_{A}(z)$ is the characteristic polynomial of $A$) are each going to end up cancelling to $0$? But the algebraic expressions we get for these $n^{2}$ entries in terms of $a_{11}$ up to $a_{nn}$ would be the same regardless of whether the $a_{ij}$ were complex or from an arbitrary field, and so if they all cancel out to $0$ for complex entries, they should do so for arbitrary field entries too, since the laws of arithmetic are all the same?$

I understood what you were asking, but the arbitrary field proofs of CH that I know of are rather short, so it seemed an odd detour to go via the complex special case.

In any case, I think you can make your idea rigorous but it takes a bit more care and precision than in your paragraph. I think something like my argument below would work, but forgive any sloppiness as my algebra is quite rusty.

Eg we would first observe that for an arbitrary matrix A over an arbitrary field K, the entries of p_A(A) are all fixed integer polynomials in the entries of A. We can map these integer polynomials to polynomials with coefficients in K by mapping the coefficients to K via the homomorphism m |-> 1+1+...+1 (m ones). The entries of p_A(A) are then given by these image polynomials evaluated at the entries of A, which are in K.

Note however that this polynomial homomorphism is not injective, because 2x and 0 both get regarded as the zero polynomial in (Z/2Z)[X] for instance.

However, in the complex case (in fact in arbitrary characteristic zero case), this mapping is injective. Hence, if the matrix has entries in C, then P_A(A) has entries that are integer polynomials in the entries of A, and if these polynomials vanish for all choices of entries, this implies they have all coefficients equal to zero. By injectivity, this implies that the the original integer polynomials have all coefficients zero and hence the entries of p_A(A) will be zero for arbitrary K.

InteGrand · Nov 22, 2016

Re: First Year Linear Algebra Marathon

$\noindent Let $d$ and $n$ be positive integers and define $f(0) = 2$, $f(d) = -1$, and $f(k) = 0$ for $k \neq 0,d$. Let $A$ be the $n\times n$ matrix with $ij$ entry $f\left(|i-j|\right)$. Find in terms of $d$ and $n$ the solution $\mathbf{x} = \begin{bmatrix}x_{1}\\x_{2}\\ \vdots \\x_{n}\end{bmatrix}$ to the linear system $A\mathbf{x} = \mathbf{b}$, where $\mathbf{b} = \begin{bmatrix}f(1)\\ f(2) \\ \vdots \\ f(n)\end{bmatrix}$.$

Paradoxica · Nov 22, 2016

Re: First Year Linear Algebra Marathon

Prove the following, for any positive integer n:

$$\noindent$ \tiny \begin{vmatrix} x+n & 1 & 0 & 0 & \ddots & 0 & 0 & 0 & 0\\ -n & x+n-2 & 2 & 0 & \ddots & 0 & 0 & 0 & 0\\ 0 & -n+1 & x+n-4 & 3 & \ddots & 0 & 0 & 0 & 0\\ 0 & 0 & -n+2 & x+n-6 & \ddots & 0 & 0 & 0 & 0\\ \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots\\ 0 & 0 & 0 & 0 & \ddots & x-n+6 & n-2 & 0 & 0\\ 0 & 0 & 0 & 0 & \ddots & -3 & x-n+4 & n-1 & 0\\ 0 & 0 & 0 & 0 & \ddots & 0 & -2 & x-n+2 & n\\ 0 & 0 & 0 & 0 & \ddots & 0 & 0 & -1 & x-n \end{vmatrix} = x^{n+1}$

good luck. you'll need it.

Linear Algebra Marathon & Questions (1 Viewer)

Well-Known Member

Well-Known Member

Well-Known Member

what

-insert title here-

what

Well-Known Member

-insert title here-

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

-insert title here-

Users Who Are Viewing This Thread (Users: 0, Guests: 1)