# Thread: Linear Algebra Marathon & Questions

1. ## Linear Algebra Marathon & Questions

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.$

2. ## 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.)$

3. ## Re: First Year Linear Algebra Marathon

Originally Posted by InteGrand
$\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}$

4. ## Re: First Year Linear Algebra Marathon

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

5. ## Re: First Year Linear Algebra Marathon

Originally Posted by dan964
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.

6. ## Re: First Year Linear Algebra Marathon

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.

7. ## 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}|$
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.

8. ## Re: First Year Linear Algebra Marathon

Originally Posted by leehuan
$\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.

9. ## Re: First Year Linear Algebra Marathon

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

10. ## Re: First Year Linear Algebra Marathon

Originally Posted by leehuan
$\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$).

11. ## 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.$

12. ## 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.$

13. ## 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.)

14. ## 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?

15. ## Re: First Year Linear Algebra Marathon

Originally Posted by InteGrand
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.

16. ## Re: First Year Linear Algebra Marathon

Originally Posted by seanieg89
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?$

17. ## Re: First Year Linear Algebra Marathon

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

18. ## Re: First Year Linear Algebra Marathon

Originally Posted by InteGrand
$\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.

19. ## 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}.$

20. ## 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.

21. ## Re: First Year Linear Algebra Marathon

i swear some of the questions here arent even first year

22. ## Re: First Year Linear Algebra Marathon

i swear some of the questions here arent even first year
amazing.

23. ## Re: First Year Linear Algebra Marathon

i swear none of the questions here are first year
ftfy.

24. ## Re: First Year Linear Algebra Marathon

First year courses have different content at different universities, and lecturers who write exams for these courses are way less constrained by things like syllabi than the people who write HSC exams.

Think of this thread as a place to post questions accessible by a first year student (on the knowledge front), with any terminology that would not be standard in all first year courses clarified.

In this sense it is similar to the advanced mx2 marathon, just you are a little less handcuffed re: the methods you can use and a higher standard of rigour is expected. And as always for these threads, I think the ideal question is more demanding on the ingenuity/creativity/intuition front than on the knowledge front.

25. ## Re: First Year Linear Algebra Marathon

Originally Posted by seanieg89
First year courses have different content at different universities, and lecturers who write exams for these courses are way less constrained by things like syllabi than the people who write HSC exams.

Think of this thread as a place to post questions accessible by a first year student (on the knowledge front), with any terminology that would not be standard in all first year courses clarified.

In this sense it is similar to the advanced mx2 marathon, just you are a little less handcuffed re: the methods you can use and a higher standard of rigour is expected. And as always for these threads, I think the ideal question is more demanding on the ingenuity/creativity/intuition front than on the knowledge front.
Amen

Page 1 of 2 12 Last

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•