Unique solution in linear fitting

[yashharsh]

I have the following question in an exercise of linear fitting.

We have [MATH]n[/MATH] linearly independent known vectors [MATH]\textbf{a}_i[/MATH], [MATH]i = 1, . . . , n[/MATH], a known vector [MATH]\textbf{b}[/MATH], and an unknown vector [MATH]\textbf{x}[/MATH]. All vectors are of dimension [MATH]m[/MATH]. Under what conditions is there a solution to the following equation? Express in terms of [MATH]m[/MATH] and [MATH]n[/MATH].

[MATH]\sum_{i=1}^{n} \textbf{a}_i\textbf{a}_i^T \textbf{x}= \textbf{b}[/MATH]
My attempt:

Let [MATH]\textbf{A} = [\textbf{a}_1, ..., \textbf{a}_n][/MATH], [MATH]m × n[/MATH] matrix
So, [MATH]\textbf{A}\textbf{A}^T \textbf{x}= \sum_{i=1}^{n} \textbf{a}_i\textbf{a}_i^T \textbf{x} = \textbf{b}[/MATH]If [MATH]m = n[/MATH], [MATH]\textbf{A}\textbf{A}^T[/MATH] is full rank and has a unique solution.

Will it have a solution if [MATH]m<n[/MATH] or [MATH]m>n[/MATH]? Why or why not? What other conditions am I missing? Am I missing condition for vector b to lie in column space of matrix [MATH]\textbf{A}\textbf{A}^T[/MATH] ?

 

[tkhunny]

If [MATH]m = n[/MATH], [MATH]\textbf{A}\textbf{A}^T[/MATH] is full rank and has a unique solution.

Semantics, maybe, but "[MATH]\textbf{A}\textbf{A}^T[/MATH] ... has a ... solution" doesn't mean anything.

So, [MATH]\textbf{A}\textbf{A}^T \textbf{x}= \sum_{i=1}^{n} \textbf{a}_i\textbf{a}_i^T \textbf{x} = \textbf{b}[/MATH]

Is [MATH]\textbf{A}\textbf{A}^T[/MATH] invertible? Does that matter?

 

[yashharsh]

Semantics, maybe, but "[MATH]\textbf{A}\textbf{A}^T[/MATH] ... has a ... solution" doesn't mean anything.

I meant to say this: For a solution to exist for the given equation, [MATH]\textbf{A}\textbf{A}^T[/MATH] should be a full rank, therefore [MATH]m = n[/MATH] is the required condition. Is it clear now?

Is [MATH]\textbf{A}\textbf{A}^T[/MATH] invertible? Does that matter?

It is not given in the question that [MATH]\textbf{A}\textbf{A}^T[/MATH] is invertible.
If we claim that [MATH]\textbf{A}\textbf{A}^T[/MATH] must be invertible, then this will imply m=n.

What we have been given is that vectors a are linearly independent. So, rank of A is n.

But I am unable to think if a solution exists if m < n or m > n, and any other conditions that I may be missing

 

[Steven G]

If we claim that [MATH]\textbf{A}\textbf{A}^T[/MATH] must be invertible, then this will imply m=n.

Did you prove your claim?

 

[yashharsh]

Before proving the claim, I need to know if showing [MATH]\textbf{A}\textbf{A}^T[/MATH] as invertible is indeed the condition for a solution to exist. Are there other conditions as well?

As far as proof is concerned, it can be like this:
Since columns of [MATH]\textbf{A}[/MATH] are linearly independent, rank of [MATH]\textbf{A}[/MATH] is [MATH]n[/MATH]. So rank of [MATH]\textbf{A}\textbf{A}^T[/MATH] in [MATH]n[/MATH]. For a solution, inverse must exist, so [MATH]\textbf{A}\textbf{A}^T[/MATH] should be full rank, so [MATH]m = n[/MATH]
What are the conditions for the equation to have a solution when [MATH]\textbf{A}\textbf{A}^T[/MATH] is rank deficient? Can this be expressed in terms of [MATH]m[/MATH] and [MATH]n[/MATH]?