linear-algebra

[spare widget]

Yes

Any D_ii!=0 if L_ii = 0

[fringe fjord]

Okay.

[spare widget]

And D_ii = 0 if L_ii != 0

[lavish jewel]

i made a counter example in octave rn

you can always construct B by taking QD

doesn't have to be QDQ^T

[spare widget]

But QD is not symmetric?

[lavish jewel]

it isn't

Q is orthogonal, D is diagonal

QD has a bunch of 0 columns

[spare widget]

Won't it break one of the requirements then?

[lavish jewel]

no

[A B] and [A; B] are full rank

and the image of B is ortho to that of A

[fringe fjord]

Do we have freedom to choose Q, or is it given?

[spare widget]

You can choose Q

[lavish jewel]

you can't actually, but you don't need it

[spare widget]

specifically the 1+ multiplicity

eigenvalues give some freedom

[lavish jewel]

up to scaling and permutation only

that's trivial

[spare widget]

scaling not because Q is ortho

[fringe fjord]

If Q is given, then I think we also need to allow D_ij = D_ji !=0 when L_ii and L_jj are both zero.

[spare widget]

Or you meant sth else probably

[spare widget]

D is diagonal

[lavish jewel]

in my understanding the original problem is rather that
[A B] and [A; B] are full rank, A is symmetric
and the image of B is ortho to that of A

[spare widget]

Yes

[lavish jewel]

if you can avoid using the EVD of A, there is no need to use it

[fringe fjord]

Oh, I guessed it was part of the question whether D would be forced to be diagonal.

[lavish jewel]

no

the question is only whether B has to be symmetric

(the answer is no)

[fringe fjord]

I still don't understand the definition of B.

[spare widget]

My guess was that B = QDQ^T, but that's just a guess

[lavish jewel]

any matrix that makes the block matrices [A B] and [A; B] both have maximum rank

B is what you want

some square matrix the same size as A, apparently

[fringe fjord]

B can at least be any invertible matrix, symmetric or not.

[lavish jewel]

then criver added the constraint that the image of B is the ortho complement to the image of A

[fringe fjord]

Ah!

[spare widget]

B cannot be invertible if A is not zero

[lavish jewel]

now if you have that you ALSO what the image of A^T to be ortho to that of B^T

then it will be symmetric (off the top of my head, at least)

but as it is, no

[spare widget]

But A is symmetric

[lavish jewel]

that's what i mean, criver

[spare widget]

So don't the images match

[lavish jewel]

what?

[spare widget]

A^T acts like A

Since it's the same

[lavish jewel]

yes, that's exactly why i wrote what i wrote?

[spare widget]

I am referring to

[lavish jewel]

yes

[fringe fjord]

Hmm, I'm not convinced. What if $A=\begin{pmatrix}I\&0\end{pmatrix}$ and $B=\begin{pmatrix}0\&E\end{pmatrix}$ as block matrices, where E is arbitrary invertible?

[spare widget]

I am still trying to digest whether QD will work

[stoic python]

Troposphere

[lavish jewel]

tropo's example works too

and is also in general not symmetric

[spare widget]

yeah, this convinced me

[lavish jewel]

not only that, but for this one, even if the images of the originals and transposes were required to be orthogonal to each other, it still wouldn't make B symmetric

so in general, no

more importantly

don't pick up the habit of just making up properties and not checking them

[spare widget]

what do you mean?

The B = QDQ^T was a guess that works, but the converse is not true (i.e. that any B is of this form), is that the property you're referring to?

[lavish jewel]

yep

[spare widget]

yeah, it is not a good habit, I am often stuck trying to prove stuff that's not true thanks to it

[formal prairie]

i think it would be full row rank, obvious since column rank = row rank and rank(A,B) = min(rank(A), rank(B)) right?

[pseudo maple]

is this true

[pine raft]

What happens when $P^n = DQ^nD{-1}$ when $n \to \infty$?

[stoic python]

ExtraterrestrialPigeon

[formal prairie]

$P^n = DQ^nD^{-1}$ when $n \to \infty$

[stoic python]

elemen

[formal prairie]

well if the eigenvalues of $P$ have magnitude less than 1, then $P^n$ tends to 0

[stoic python]

elemen

[formal prairie]

otherwise it's unbounded

[halcyon spindle]

I did a bit of clarification on A field has no divisors of zero. I already know it's referring to for any x, y in a field K, if xy = 0 then either x = 0 or y = 0. I have proven this. It's just the wording "has no divisors of zero".

I am thinking of it in the sense of elementary number theory and it's confusing me.

[fringe fjord]

The usual term in English is a "zero divisor".

[halcyon spindle]

ah I see, thanks.

[pine raft]

but $P^0 = SD^0S^{-1} = SS^{-1} = I$?

[stoic python]

ExtraterrestrialPigeon

[pine raft]

Are we saying that n is bounded $0 \le n \le 1$?

[stoic python]

ExtraterrestrialPigeon

[formal prairie]

no, n tends to infinity. if the eigenvalues of P have magntiude less than 1 then P^n tends to 0

[pine raft]

So something like $||x|| = \sqrt{Q}$ where Q defines some rational number?

[stoic python]

ExtraterrestrialPigeon

[pine raft]

Are there no bounds to this then, even if it's on an open interval as long as the magnitudes have a value less than 1 then it tends to 0?

[lavish jay]

Solving x' and y' for X and Y the solution for this problem is x'= Ysin + X cos ; y' = Ycos - Xsin

?

my book don't have the answer for this problem

[spare widget]

this is a rotation matrix:

$\begin{bmatrix} x \ y \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta \ \sin\theta & \cos\theta \end{bmatrix} \begin{bmatrix} x' \ y' \end{bmatrix}$

[stoic python]

criver

[spare widget]

the inverse is the transposed

$\begin{bmatrix} x' \ y' \end{bmatrix} = \begin{bmatrix} \cos\theta & \sin\theta \ -\sin\theta & \cos\theta \end{bmatrix} \begin{bmatrix} x \ y \end{bmatrix}$

[stoic python]

criver

[spare widget]

it's also the same as setting theta = -theta

i.e. a rotation by angle theta is undone by a rotation by angle -theta

[formal prairie]

i think so...

[shut tree]

if M is 3x2 matrix, how do I show that these are equivalent?

I know if that M1 and M2 are linearly independent, then if $a_1 M_1 + a_2 M_2 = 0$, then $a_1=a_2=0$

[stoic python]

bubbly cat

[shut tree]

but how do I show the 1st one with the others?

[spare widget]

Suppose there exists a vector (s,t) != (0,0)

Such that s * M1 + t * M2 = 0

without loss of generality assume s!= 0 -> M1 = t* M2 / s, they are linearly dependt (you don't evenneed to do this division part but I think it's clearer)

Since there is no such vector -> kernel = {0}

[shut tree]

sure I get how b and c are connected

but idk how rank 2 ties into this

i mean I do get it kinda but idk how to show it

[spare widget]

Well how is rank defined in your book

I assume it is defined as the dimension of the col/row space

[shut tree]

any basic definition works

[spare widget]

But if the two vectors are independent the the dimension of the space spanned by their lin comb is 2

The a,b,c parts are actually quite tautological

[shut tree]

yea

[spare widget]

In the sense that a) b) c) are the same once you write the definition

I don't even know what there is to prove, unless you have a funny definition of rank in your book

[shut tree]

💀 not for a math class

so i guess it just wants us to understand it

lol

[spare widget]

You write the def of kernel, the def of lin indep, the def of rank, and you see the requirements are the same

[shut tree]

yea i noticed theres a lot of equivalent definitions for some reason

[spare widget]

Lin indep means there are no (s,t) != (0,0) such that s * M + t * M2 = 0, but the kernel is made only of vectors for which s * M1 + t * M2 = 0

Thus kernel= {(0,0)}

the column rank of M is the dimension of the image

but M1, M2 are independent -> 2

[shut tree]

oh ok thanks

[spare widget]

I think it's trying to get you familiar with the definitions

You're supposed to write ot the definitions of all 3 ad think what those mean

[shut tree]

yea I think this was supposed to be mostly review (but I kinda forgot it all lol)

[spare widget]

Lin indep of a set of vectors v1,...,vn <-> sum_i s_i * v_i = 0 only for (s1,...,sn) = (0,...,0)

kernel(M) = {v : Mv = 0}

column-rank of M -> the dimension of the column space of M -> column space M = span(M1,...,Mn) = {\sum_i s_i * M_i}

then you get to the definition of dimension and basis

It's testing basic definitions

[shut tree]

sure I still remember that I think yea

[spare widget]

Just go through the first chapter of axler or any similar lin alg book

[west oak]

PLEASE Explain this

[wintry steppe]

this is not linear algebra

[gritty swift]

given a vector space $V$ with subspace $U$ and a linear map $T : U \to W$ can we extend $T$ to be defined on all of $V$ without assuming $V$ or $W$ is finite?

[stoic python]

uli

[gritty swift]

this is equivalent to showing there exists another subspace $\tilde U$ of $V$ such that $V = \tilde U \oplus U$ since then we could define $T$ on $\tilde U$ no problem

[stoic python]

uli

[teal grotto]

sure, every vector space has a basis

just keep extending

[gray dust]

^this holds if aoc is assumed

[gritty swift]

oh ok, is it false without aoc?

[gray dust]

yes

[gritty swift]

neat

[gray dust]

the matter of extension in infinite dim spaces came up recently

#linear-algebra message

coys comment on aoc below

[teal grotto]

"every vector space has a basis" is equivalent to aoc, so if you dont accept aoc, then there must be a vector space which has no basis

[gritty swift]

ooh cool

[shut tree]

What does a multilinear function mean?

[teal grotto]

linear in each component

an example of a bilinear function is a real inner product

[shut tree]

So its just bilinear

is that what it means

[gray dust]

bilinear is specific case of multilinear

[shut tree]

ohh ok I get you now

[gray dust]

2 slots, linear in each

[teal grotto]

if you want to specify, you could say n-linear function

[shut tree]

got it thx

So what's the motivation for tensors? I see that theres a bunch of definitions but idk how they are motivated

like I see duals, exterior tensors, tensor products, but idk the point of them

[gritty swift]

I've been thinking that isomorphisms are more intuitive then dimension arguments and I'm wondering why axler doesn't use them when talking about duality, here's a quick draft of how I think about duality with isomorphisms https://uli.rocks/p/duality-done-right which I think its more elegant then axler's dimension juggling proofs

I've probably missed something or maybe axler does it for pedagogy reasons in case people skipped the previous section, idk

[teal grotto]

one motivation for tensors is to define differential forms and to investigate what the right type of objects to integrate over a manifold are.

[shut tree]

ah I guess I am not at that level to see it motivated yet (soon though maybe)

[teal grotto]

why do you say "duel" space and not dual space on this page

[gritty swift]

uhh oops that's embarrassingly bad spelling

[teal grotto]

i think its kinda funny

[tired fossil]

hey guys, im confused, for b im doing it, but it says the answer is (x+y,0,y+z) not sure how they got that

ignore, i didnt see that pattern

[wintry steppe]

so you all good ?

[tired fossil]

yea, i was tripping

[wintry steppe]

They are used alot in differential geometry

To talk about curvature

There are also alot of examples in physics

[subtle walrus]

it's just an easy way to describe multilinear relationships

in the most general definition it reduces the study of multilinear maps to the study of linear maps

which is really nice, because you only have to worry about the latter and not 2-linear, 3-linear, etc separately

[spare widget]

I have seen the notation M_{ij} for denoting minors of a matrix (row i removed and column j removed). Is there some standard notation for removing multiple row/columns?

For example if I have diagonal matrices C1 and C2 with 1s and 0s on the diagonal, the C1 M C2 would produce a matrix with a maximum of |C1| non-zero rows and |C2| nonzero columns - and I want to extract those in a reduced matrix with the 0 rows and cols removed.

Would $M|_{C_1 \times C_2}$ makes sense as notation for this?

[stoic python]

criver

[spare widget]

Or is there something standard

[lavish jewel]

you can make up whatever notation you like as long as you explain it clearly

i can't think of anything standard off the top of my head

what you could do is make C1 and C2 rectangular instead of square

e.g. for C1, remove all rows that are 0 vectors

similarly for the columns of C2

then you would take C1 M C2

and that product gives you what you want

[spare widget]

I am aware that I can write it as a restriction and prolongation operator, the problem is that C1 and C2 change coefficients in my problem, so I generally have to keep them square. Though if there's no established notation I guess I will just define this as suggested.

[lavish jewel]

you could still do that in code

no reason to use a matrix for it

you can represent the linear transformation in a matrix free fashion through indexing

much in the same way you want to do it on paper

then what you'd want is a function that takes in M and two lists of indices

then it slices M up based on those lists

[spare widget]

Thanks. I am not yet at the code part though

[lavish jewel]

now that we bring this up, you do see a lot of notation of the form $\boldsymbol{M}_\mathcal{I}$, for example

[stoic python]

Edd

[lavish jewel]

where \mathcal{I} is an index set

[spare widget]

Of tuples?

[lavish jewel]

hmm?

[spare widget]

(i,j) in I

[lavish jewel]

i was gonna suggest the notation $\boldsymbol{M}_\mathcal{I}^\mathcal{J}$

[stoic python]

Edd

[lavish jewel]

where you keep the rows of M indexed by I, and the columns indexed by J

[spare widget]

I think they'd usually put I top, J bottom

[lavish jewel]

however you like 😛 you could also just stick to the one you proposed

as long as the notation is explained clearly somewhere, you can really use whatever you prefer

but i think what you said matches the covariant/contravariant convention

[spare widget]

I meant in the context of physics they have row indices top and col indices bottom for (1,1) tensors. But it seems reasonable notation too, thank you.

[lavish jewel]

right

[zinc timber]

tensors

[gritty swift]

can't you represent multilinear maps by a linear map on the product type? or am I missing something

[zinc timber]

are you talking about tensor products?

[subtle walrus]

a bilinear map A x B -> C corresponds to a unique linear map A tensor B -> C

this is what i meant

[stoic python]

Patrick Bateman

[spare widget]

check whether they are linearly dependent

put them in a 3x4 matrix

and apply elementary operations to bring them to reduced echelon form

if all rows remain at the very end

then it's all 3 vectors

if one row is zero

then take the other two rows

if two rows are zero

then take the only remaining one

you are basically given a set of vectors

and you want to find a minimal set of vectors that span the same subspace as those

a basis is made up of linearly independent vectors

if you have linear dependence then you have a frame/overcomplete basis instead

the usual for these exercises is that they give you a frame/overcomplete basis and you need to reduce it to a basis

I would stack them horizontally

and then perform row ops

you can of course work with the above too, but you'll have to perform col ops

it does matter when you start juggling variables around if you have a linear system of equations, it's a pain changing the order of your variables

just use the transpose and apply row ops

then they are linearly independent

they simply didn't remove the 0s like you did it seems

but since the vectors are linearly independent

then even the initial are fine

(1,1,-4,-3), (2,0,2,-2), (2,-1,3,2)

the issue is when they are not linearly independent

then you take out only the non-zero rows

if they are dependent then the matrix would not have full row-rank

i.e. you'll get a zero row

at some point through elementary transformations

you can get all rows except 1 to be zero

that would be the case if all vectors lie on a single line

e.g. when they are multiples of each other

then taking a single one of the initial vectors is fine

[spare widget]

the number of non-zero rows would be the dimensionality of the spanned subspace

e.g. 1 -> single line passing through the origin

2 -> 2d plane passing through the origin

3 -> 3d hyperplane passing through the origin and so on

you need only k independent vectors to span a k-dimensional subspace

anything more would be linearly dependent

i.e. you'll get a frame/overcomplete basis

[minor fox]

How do I create a matrix that transforms a normal vector to <0, 0, 1> and rotates all other vectors accordingly?

Do I just write out the product of two rotation matrices and the normal vector and then solve for the angles? Is there a better way?

[spare widget]

What is a normal vector

There is a better way

[minor fox]

Like you can just take it to be any arbitrary vector I think

Assuming it's not the 0 vector

And it has length 1

[spare widget]

Let n be unit length and let it be orthogonal to f1,...,f_n and you are looking for R such that n' = R n, where n' is also unit length. Compute gi = fi - dot(fi, n') / (1 + dot(n,n')) * (n+n').

So the matrix is

[minor fox]

n' should be 0 0 1

This is in R^3

[spare widget]

$R= I - \frac{1}{1+n^Tn'}(n+n')n^T$

[stoic python]

criver

[spare widget]

If I didn't mess up something

[minor fox]

Can you explain what this is doing?

So this transforms n to n'?

[spare widget]

Also n' cannot be allowed to be -n

[minor fox]

I think that would be a problem

[spare widget]

Since then there are infinitely many rotations that fit the bill

[minor fox]

A normal vector could certainly be 0 0 -1 and I would want to transform that to 0 0 1

[spare widget]

There are infinitely many rotations that do this

You can pick any one of those in that singular case

What I wrote picks the minimal rotation in terms of angle

[minor fox]

Well, I would like to know how what you wrote works

[spare widget]

But there are infinitely many 180 degree rotations

it considers the 2d plane formed by n and n'

And then does some projections

[minor fox]

I don't understand

[spare widget]

A rotation changes only the components of a vector parallel to the rotation plane

So you decompose fi = fi_parallel to_plane + fi_orthogonal_to_plane

[zinc timber]

where are you getting this matrix

[spare widget]

From this

The matrix is some kind of rejection operation afaik

[minor fox]

I think it would help to just set n' to 0 0 1 since that's what I'm concerned with

[spare widget]

I can try to write out the whole derivation if you give me some time

[zinc timber]

I would like to see the derivation

[minor fox]

Yeah, if you are getting this from somewhere I would also like a link. I don't understand your explanation

[spare widget]

I am getting it from my memory 😂

[minor fox]

This makes sense

https://stackoverflow.com/questions/10798954/how-to-rotate-a-vector-to-a-place-that-is-aligned-with-z-axis

Dot n with z to get angle. Cross n with z to get axis. Convert to axis-angle rotation matrix

[spare widget]

the above would work, but it will break also for n = n'

[minor fox]

Yeah, so if n = n' just do nothing

[spare widget]

also breaks for n=-n' as mine does

anyways

here goes the derivation

you have your two unit vectors n, n' and provided they are not linearly dependent they span a 2D plane

now say you have a vector orthogonal to n, e.g. vector v

decompose it into a piece parallel to the plane and a piece perpendicular to it

$v = v_{\perp} + v_{\parallel}$

[stoic python]

criver

[spare widget]

I also want to decompose v_parallel in an orthonormal coordinate system

to get that orthonormal coordinate system I would find n_perp that lies in the plane spanned by n,n' and is perpendicular to n

$n_{\perp} = (n'-(n^Tn') n) / \sqrt{1-(n^Tn')^2}$

[stoic python]

criver

[spare widget]

now I can write:

$v_{\parallel} = (n^Tv)n + (n_{\perp}^Tv)n_{\perp}$

[stoic python]

criver

[spare widget]

but n^Tv = 0 since I started with the assumption that they are orthogonal

thus

$v_{\parallel} = (n^T_{\perp}v)n_{\perp}$

[stoic python]

criver

[spare widget]

The rotated vector v' can be decomposed in a similar way

$v' = v'{\parallel} + v'{\perp}$

[stoic python]

criver

[spare widget]

and then in a similar way we get

$v_{\parallel}' = ((n'{\perp})^Tv')(n'{\perp})^T$

[stoic python]

criver

[spare widget]

and since the rotation doesn't affect the orthogonal parts

then

$v'{\perp} = v{\perp}$

[stoic python]

criver

[spare widget]

so at the end you get:

$v' = v'{\parallel} + v'{\perp} = (n'{\perp})^Tv')n{\perp}' + v_{\perp} = (n_{\perp})^Tv)n_{\perp}' + v - v_{\parallel} = v + ((n_{\perp})^Tv)(n'{\perp}-n{\perp})$

[stoic python]

criver

[spare widget]

let me see if I wrote everything correctly

I think I did, now if you plug in the definitions of n_perp and n'_perp you should be able to simplify some terms and end up with what I had

there's probably an easier way to derive the same thing, I am not sure

the key points used are that $v'{\perp} = v{\perp}$ and $n'{\perp}\cdot v' = n{\perp}\cdot v$ which follow from the requirement of this being a rotation

[stoic python]

criver

[spare widget]

i.e. rotation leaves the space orthogonal to the rotation plane untouched, and angles and lengths are preserved/the dot product being preserved, since x'^Ty = x^TR^TRy = x^Ty

if you don't simplify the final expression

then you're left with

$v' = v + (n_{\perp}\cdot v)(n'{\perp}-n{\perp})$

and if you expand the n_perp and n'_perp in terms of n and n'

you get a term sqrt(1-(n^Tn')^2) in the denominator

which would result in a 0 for n=n' or n=-n', doing some simplifications gets rid of the n=n' singularity

but the n=-n' singularity remains

but this is clear, since there are infinitely many "shortest" rotations that get from n to n' if those are at a 180 angle

[stoic python]

criver

[spare widget]

the simplified version (after plugging the definitions for n_perp and n_perp') is

$v' = v - \frac{n'\cdot v}{1+n'\cdot n}(n'+n)$

[stoic python]

criver

[spare widget]

and if you were to extract the matrix from this you get

$v' = \left(I - \frac{1}{1+n'\cdot n}(n'+n)n^T\right)v$

[stoic python]

criver

[spare widget]

I think something can be done to modify it further to make it work for v not perpendicular to n

actually I think that's trivial

one just needs to remove the v_perp part, apply the above matrix, then add the v_perp part back, actually maybe it's not that simple, since this would refer to the perp part to n and not to the plane

[robust pond]

@jagged crown i figured out that reduction problem after thinking abou it a lil more https://www.emathhelp.net/en/calculators/linear-algebra/reduced-row-echelon-form-rref-caclulator/?i=[[1%2C1%2C-1]%2C[2%2C8%2C-6]]&reduced=on

we just needed to multiply 2 by its output of x before moving

if u care

[formal prairie]

b is in the span of the columns of A

[jagged crown]

ty! ill check it out after my test

[spare widget]

For a symmetric positive definite matrix $A$ one has the optimal step size for gradient descent: $\gamma = \frac{\boldsymbol{r}^T\boldsymbol{r}}{\boldsymbol{r}^T\boldsymbol{A}\boldsymbol{r}}$ where $\boldsymbol{r} = \boldsymbol{b}-\boldsymbol{A}\boldsymbol{x}$.

[stoic python]

criver

[spare widget]

For solving Ax = b

is there a similar result for nonsymmetric matrices (also for symmetric but indefinite)

[lavish jay]

Need help in problem 3

My question is

i don't understand where i should place this 1 unit of production from sector 1

[chrome radish]

Let (u, v) be the Euclidean inner product $R^2$, and let $u=(2, -1), v=(-1, 3), w=(0,-5)$. Verify that $(u+v,w) = (u,w)+(v,w)$. I got $$(u+v,w)=(2 \cdot 0+(-1) \cdot (-5))+((-1) \cdot 0+3 \cdot (-5))=-30$$

[stoic python]

John doe

[chrome radish]

but according to my textbook the answer is equal to 0. I have no idea what I did wrong here. For me it doesen't look like I did anything wrong

[formal prairie]

u+v = (1,2)

<u+v,w> = -10

<u,w> = 5

<v,w> = -15

[chrome radish]

dont you just do $(u+v,w)=(u_{1}w_{1}+u_{2}w_{2})+(v_{1}w_{1}+v_{2}w_{2})$

[stoic python]

John doe

[formal prairie]

yea

u can do that

[chrome radish]

thats what I did

if you look at my answer

[formal prairie]

your arithmetic is wrong

[chrome radish]

what did I do wrong?

[formal prairie]

$2 \cdot 0+(-1) \cdot (-5)+(-1) \cdot 0+3 \cdot (-5)=-30$

[stoic python]

elemen

[formal prairie]

^ wrong

5 + (-15) = -10

[chrome radish]

what

the answer isn't -10

[wintry steppe]

you get 0 if you do <u, v+w>

[chrome radish]

can you show me ur work

[wintry steppe]

my work ?

wdym

[chrome radish]

how did you get it to 0

[wintry steppe]

I computed

first you add the two vectors v and w

v+w = (-1,-2)

then you compute dot product between u=(2,-1) and (-1,-2)

[chrome radish]

I see, but my textbook did: $(u+v,w)=(u{1}w{1}+u{2}w{2})+(v{1}w{1}+v{2}w{2})$

[stoic python]

John doe

[wintry steppe]

your textbook is wrong

I mean, that should give -10 as pointed out above

[tired fossil]

hey, i am having trouble understanding this proof, can anyone help?

[wintry steppe]

where is the proof ?

[spare widget]

write out how U^perp is defined

and use U directsum U^perp = R^n

[stoic python]

DarQ (Shuri for honorable)

DarQ (Shuri for honorable)

DarQ (Shuri for honorable)

[subtle walrus]

plug into definition

[molten pilot]

wdym

which definition

[subtle walrus]

of linear independence

$\lambda_0\cdot 1 + \lambda_1 \cdot x + \dots + \lambda_k \cdot x^k = 0$, show that all lambdas are 0

[spare widget]

sum_i c_i x^i = 0 <-> c_i = 0

[stoic python]

Lochverstärker

[molten pilot]

oooh

[subtle walrus]

this follows immediately for degree reasons

[molten pilot]

k, got it

thanks

[spare widget]

you can also show its isomorphic to R^{k+1}

[plush canyon]

I have a super tough question

I don't know if the teacher wrote it wrong or what

It was 3biii

[spare widget]

So what's the issue?

[plush canyon]

Can someone assist because NOBODY I know got it right

I've wrote down the Matrix

So how do i reflect it

B

[spare widget]

It's a line passing through the origin

Project a vertex on it

Let the vertex be v

And the projection be v'

[spare widget]

Then the reflection is v'' = v' + (v'-v)

It's asking you to make

[plush canyon]

U want me to take the partial derivatives basically

[spare widget]

no

[plush canyon]

So i have w=8i+j

[spare widget]

$v = v_{\parallel} + v_{\perp}, \quad v_{refl} = v_{\parallel} - v_{\perp}$

[stoic python]

criver

[plush canyon]

Ok I get this

I understand that

[spare widget]

The parallel and perp refers to parallel and perp to the line

[plush canyon]

Yes

But how does the 8i+J

Fit it

Fit in

[spare widget]

The line passes through the origin and is parallel to (8,1)

[plush canyon]

One moment

This passes through

This is parallel to (8,1)

[spare widget]

Idk what that array of numbers is

[spare widget]

Do you understand how to compute v_perp and v_parallel given v?

[plush canyon]

I'm not sure but I don't think that's right. I probably could

[plush canyon]

Can u open this?

[spare widget]

No

[plush canyon]

That's the full question there

[spare widget]

Do you know how to compute the projection of v onto the line?

[plush canyon]

I have done a. Bi and bii

No because Idk what v us

V is

[spare widget]

v is an arbitrary point in space

[plush canyon]

Omg math teachers need to explain shit better

[spare widget]

A vector

[plush canyon]

In my uni

Ok

A vector

Right

[spare widget]

Do you know how to project it onto the line passing through (0,0) and parallel to (8,1)?

[plush canyon]

Y-b=m(x-a)

[spare widget]

Have you studied dot product

[plush canyon]

This isn't even a dot product question

Wtf

Scaler product we call it

This is

A reflection

[spare widget]

Sure you can use the reflection matrix that is presented there probably

It's probably more useful to understand how to derive it yourself though

[plush canyon]

Well my teacher sucks

I couldn't derive anything myself

Can u teach me sir?

[spare widget]

To project a vector onto another vector, you can use dot(v,u) * u, where u is unit length

[plush canyon]

I see

Ok

[spare widget]

Then dot(v,u) * u is the projection of v onto this unit length vector

And you can split v into

$v = v_{\parallel} + v_{\perp} = (v\cdot u) u + v_{\perp} \implies v_{\perp} = v - (v\cdot u)u$

[stoic python]

criver

[spare widget]

u should be the normalized version of (8,1)

The reflection is

[plush canyon]

Wait

Question here

[spare widget]

$v' = v_{\parallel} - v_{\perp}$

[stoic python]

criver

[spare widget]

Try drawing a picture

[plush canyon]

U can split v into to because its projecting 2 ways. If u look at it like that

One projection on another and vice versa?

[spare widget]

I am splitting v into a component parallel to the line, and a component orthogonal to it

Try drawing it

[plush canyon]

Ok

Right

U want me to draw it on the hexagon?

[spare widget]

No

Just draw it for yourself

[plush canyon]

Ok

[spare widget]

Having 2 vectors, one unit length

[plush canyon]

Wait

[spare widget]

And then projecting a vector onto it

[plush canyon]

Unit lenght

What does this mean.

[spare widget]

https://en.m.wikipedia.org/wiki/Vector_projection

[plush canyon]

I see

That picture makes sense

The green is parallel

The red is orthogonal

[spare widget]

You should also try drawing: v = v_parallel + v_perp, u, and v' = v_parallel - v_perp

[plush canyon]

Ok

But that's for part c in my question

For iii I just need the coordinates

And then I'll be able to understand it better then

How do I get the reflected ones?

[spare widget]

It's not for your question, it's so that you will understand what I was explaining visually

[plush canyon]

Right

No I get this drawing

Yes I understand it.

[spare widget]

Then you should have no trouble continuing it on from this point

[plush canyon]

I am having trouble

Because I don't understand what u told me relates to my question

[spare widget]

what does this do?

What is v'

[plush canyon]

Gets you the original line

[plush canyon]

This

[spare widget]

Yes what is this

Geometrically

[plush canyon]

The original projection

[spare widget]

Draw it

[pseudo maple]

is (undefined-0.5) semi-stable as a s classigication?

[spare widget]

And you'll figure it out

[pseudo maple]

how do you classify something that is undefined? in directiona fields

[spare widget]

Just draw v, u, v', v_perp, v_parallel

[tired jungle]

What does a tangent bundle of a surface s look like?

Is it just all lines perpendicular to it

[plush canyon]

Criver

I loved your expiation

But did not understand what any of that had to do with my hexagon matrix question.

Could u walk me through my question step by step and then explain why u taught me what u did?

I want to understand

[plush canyon]

Why wanted me to use this.

The teacher never taught that.

[spare widget]

Did you draw it

[plush canyon]

Yes

[spare widget]

So what is v', you can post you drawing btw, I can check whether it's correct

[plush canyon]

There

[spare widget]

draw u, denote v_perp and v_parallel, and then draw v'

[plush canyon]

Ok

[spare widget]

That's wrong, also they should be all on a single drawing

You should use

v_parallel = v projected on u = (v dot u) * u

[plush canyon]

Why does the drawing relate to my hexagon. I don't get it.

[spare widget]

v_perp = v - v_parallel

[plush canyon]

The teacher NEVER taught this

[spare widget]

Because the hexagon has vertices

If you're able to reflect an arbitrary vector v

[plush canyon]

I get it

[spare widget]

Then you'll be able to reflect any of the vertices using the same approach

[plush canyon]

I can reflect on the hexagon

But the hexagon is given in matrix form?

[spare widget]

You can reflect all of the hexagon's vertices using this approach

[plush canyon]

Ok

[spare widget]

It's irrelevant that the vertices are ordered in a matrix

At the end of the day they are represented through 2d vectors

[plush canyon]

Why is this approach better than

[plush canyon]

What's written here

[spare widget]

look, draw u and draw v with their tails at the origin

Then draw the projection of v onto u

The projected part is v_parallel, the perpendicular part is v_perp = v - v_parallel

[plush canyon]

Ok

I'll try again

Idk

[spare widget]

where you have v_parallel = projection of v on u = (v dot u) * u

v_perp = v - v_parallel, and v' = v_parallel - v_perp = (v dot u) * u - v + (v dot u) * u = 2 * (v dot u) * u - v

thus the matrix is:

$v' = \left(\frac{2}{|u|^2}uu^T - I\right)v$

[stoic python]

criver

[spare widget]

$M = \frac{2}{|u|^2}\begin{bmatrix}u_1^2 & u_1u_2 \ u_1u_2 & u_2^2 \end{bmatrix} - \begin{bmatrix} 1 & 0 \ 0 & 1 \end{bmatrix}$

[stoic python]

criver

[spare widget]

which is exactly the matrix that you have here

but I have added a normalization factor too, in case u is not unit length (i.e. |u|!=1)

in your case u = (8,1) is not unit length

multiplying every vertex by the matrix, would yield you their reflections

I highly recommend going over some basics on vectors and analytic geometry since you seem to be struggling with that

I can suggest this as something that should be fairly simple and with enough pictures: http://immersivemath.com/ila/index.html

[tired fossil]

hey, can someone help me understand c? I don't know how to prove this

[spare widget]

$q(x) = \sum_{i=0}^n b_ix^i = \sum_{i=0}^n a_ix^i + \sum_{i=1}^n i a_i x^i = p(x) + xp'(x)$

[stoic python]

criver

[spare widget]

Idenitfy b_i = a_i(1+i)

then a_i = b_i /(1+i) and you're done

[tired fossil]

so, b_ix^i is q(x)? just to make sure

[spare widget]

Yes

I picked b for the coef of q and a for the coef of p

All you have to do is expand the polynomials and the derivative

[tired fossil]

okay, give me a sec

i have q(x)=p(x)-xp'(x) written out, so, where do i go from here?

[spare widget]

they have written q(x) = p(x) +xp'(x)

Now set q(x) = sum_i b_i x^i and p(x) = sum_i a_i x^i and substitute in the equality

[tired fossil]

i wrote them out with the sums already done, got b_1+...+b_n x^n= a_0+2a_1 x+...+(n+1) a_n x^n

how do i finish the proof from here?

[spare widget]

It's wrong though

What you wrote is wrong

[tired fossil]

am i setting p(x) to q(x)?

can you explain why I would do that?

what about this, can someone help guide me through this one?

[formal prairie]

For any vector $x \in U, x = a_1 f_1 + \dots a_m f_m$

[stoic python]

elemen

[formal prairie]

$U^\perp$ is all vectors $y$ such that $x^\top y = a_1f_1^\top y + \dots + a_mf_m^\top y = 0$

[stoic python]

elemen

[formal prairie]

so if we define the matrix $ A = [f_1, f_2,\dots,f_m]$ then y must be in the nullspace of $A^\top$

[stoic python]

elemen

[formal prairie]

and now you can show that $f_{m+1},\dots,f_{n}$ is a basis for the nullspace of $A^\top$

[stoic python]

elemen

[formal prairie]

^ I'm not sure if all my steps are right but hope it helps

[tired fossil]

what is the symbol above x in this

[tired fossil]

.

[formal prairie]

transpose

[tired fossil]

fml, i haven't seen that at all this unit

[formal prairie]

transpose just converts column vector to row vector and vice versa.

[tired fossil]

yep, but not sure how to use it bevcause i haven't been asked to use them once

[formal prairie]

okay you can just replace $x^\top y$ with $<x,y>$

[stoic python]

elemen

[formal prairie]

<x,y> is inner product

[gritty swift]

the transpose exchanges rows and columns in a matrix, it works the same for vectors since column vectors are (n by 1) matrices and row vectors are (1 by n) matrices

and vise versa. this is especially useful because $x^Ty$ denotes the dot product
$$
x^Ty = \begin{bmatrix}
1 \ 2 \ 3
\end{bmatrix}^T
\begin{bmatrix}
3 \ 4 \ 5
\end{bmatrix}
= \begin{bmatrix} 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} 3 \ 4 \ 5 \end{bmatrix}
= 1\cdot 3 + 2\cdot 4 + 3\cdot 5
$$

[stoic python]

uli

[gritty swift]

via the same matrix multiply rule you're hopefully familiar with

http://matrixmultiplication.xyz/ is a nice way to think about it btw

[tired fossil]

not really confused abot that part, just what the last person wrote out, like this proof makes literally no sense to me. I just can't crack it

I've tried it for a day and a half now

[gritty swift]

well, by the definition of span we need only show every $u \in U^{\perp}$ can be written $u = a_1\mathbf f_1 + \dots a_n\mathbf f_n$ for some $a_n$

[stoic python]

uli

[gritty swift]

since every $u \in U^{\perp}$ is also in $\mathbb R^n$ we can write $u$ as a combination of the basis for $\mathbf R^n$
$$
u = a_1 f_1 + \dots + a_nf_n
$$

[stoic python]

uli

[gritty swift]

(oops, in the first message I sent I should have used m for the final subscript, ignore that)

anyway, since $u \in U^{\perp}$ is perpendicular to every $f_1,\dots,f_m$ in $U$ we must have $\langle u, f_j\rangle = 0$ for $1 \le j \le m$

[stoic python]

uli

[gritty swift]

(oops in the first message I should have said we want to show $u = a_{m+1}f_{m+1} + \dots + a_nf_n$ ignore that)

[stoic python]

uli

[gritty swift]

using the linearity of the inner product and writing u as a combination of f1,...,fn as above gives
$$
\langle u, f_j\rangle = a_1\langle f_1, f_j\rangle + \dots + a_n\langle f_n, f_j\rangle
$$
since the basis is orthogonal, $\langle f_k, f_j\rangle = 0$ for $j \ne k$ leaving us with
$$
\langle u, f_j\rangle = 0 = a_j\langle f_j, f_j\rangle
$$

[stoic python]

uli

[gritty swift]

(this is why orthogonal bases are so nice)

[tired fossil]

inner product is dot product correct?

[gritty swift]

yes

since $\langle f_j,f_j\rangle > 0$ this shows $a_j = 0$ for all $1 \le j \le m$

[stoic python]

uli

[gritty swift]

which turns this into
$$
u = a_{m+1} f_{m+1} + \dots + a_{n}f_{n}
$$
as desired.

[stoic python]

uli

[gritty swift]

I wrote out all the steps in a ton of detail but really it consists of like 2 steps

1. write $u = a_1f_1 + \dots + a_nf_n$ for $u \in U^{\perp}$

2. dot both sides with $f_j$ for $1 \le j \le m$ to get $\langle u, f_j\rangle = 0 = a_j\langle f_j, f_j\rangle$ implying $a_j = 0$

3. hence $u = a_{m+1}f_{m+1} + \dots + a_nf_n$ meaning $u \in \text{span}(f_{m+1}, \dots, f_n)$ so $U^{\perp} = \text{span}(f_{m+1},\dots,f_n)$ as desired.

[stoic python]

uli

[tired fossil]

can you explain the second part

what is <f_k,f_i>?

[gritty swift]

the dot product between f_k and f_i, which is zero since f_1, ..., f_n is an orthogonal basis

[tired fossil]

which is set is f_k? or is that arbitrary?

[gritty swift]

you were given that f1, ..., fn is an orthogonal basis of R^n

[tired fossil]

so f_k is that entire set

or basis

[gritty swift]

f_k denotes the kth element in f_1,...,f_n. in this post it's saying the only term that isn't zero is the f_j, f_j one

because the others die from orthogonality

$$
\langle u, f_j\rangle = a_1\langle f_1, f_j\rangle + \dots + a_n\langle f_n, f_j\rangle = 0 + \dots + a_j\langle f_j, f_j\rangle + 0 + \dots + 0
$$

[stoic python]

uli

[gritty swift]

basically any argument involving orthogonal vectors will involve taking a dot product at some point and cancelling a bunch

[tired fossil]

how do know <f_i,f_i> =0?

[gritty swift]

? it isn't, <f_i, f_i> is the length ||f||^2

you mean <f_i, f_j> = 0

and that's true by the definition of orthogonal

you might be used to seeing it as $f_i^Tf_j = 0$

it's the same thing

[stoic python]

uli

[tired fossil]

this

or am i blind

[gritty swift]

it's greater then zero

because the length of f_j is nonzero

you need that to show aj = 0 rigorously

[tired fossil]

i thought it could =0 as well

[gritty swift]

only if f_j is zero, which it can't be because it's part of the basis f_1, ..., f_n

ie. if it were zero the list f_1, ..., f_n would be linearly dependent hence not a basis

[tired fossil]

oh okay, that makes sense, because a 0 vector cannot be a part of a basis

thank you!

[gritty swift]

np

[mossy coral]

Not quite math but I know alot of people use latex here. Does anyone know how to write matrix in respect to a,b basis in latex

[nocturne jewel]

$[T]_a^b$ for transformation T

[stoic python]

Mosh

[nocturne jewel]

that's standard notation for $T:V\to W$ with basis of V a, basis of W b

[stoic python]

Mosh

[nocturne jewel]

(iirc at least)

[mossy coral]

ty

[tired jungle]

How do I show that all norms are equivalent?

in R^n

[teal grotto]

first show that every norm is continuous.

show that the max norm unit ball {x in R^n : |x|_{max} = 1} is compact in R^n.

then show that every norm is equivalent to the max norm. for one direction, make use of the fact that R^n is finite dimensional, i.e., it has a finite basis. for the other direction, use the extreme value theorem

[fringe fjord]

You can just show directly that every open ball according to N1 contains some open ball according to N2, for arbitrary norms N1 and N2. No need to give special status to the max-norm.

The key step is to decide on the radius of the N2-ball, which you can do by comparing the N1 and N2 lengths of each basis vector, and using the triangle equality to find an upper bound for the N1-length of a vector that fits in the N2 unit ball.

Hmm, no, actually I'm talking nonsense. The direct way I was imagining won't work for an arbitrary basis. Ignore, sorry.

[coral geyser]

Wait can someone try to find this constraint

[fringe fjord]

How did you find the one you already have?

I would do Gaussian elimination on your matrix. That ends with two rows that have zeroes in the first three columns and a combination of xyzt in the last. Those two combinations clearly need to vanish for the last column to be a linear combination of the three first.

If you only get one row of constraints, you must have made a mistake along the way.

[coral geyser]

yeahh nah

it was fine

i was doing this for a friend and we were just stumped with the nasty row echelon form

but if u keep the rows in the same place and not do it through an adhoc method

it comes out nicely somehow lol

[queen geode]

hey how would I go about putting a system of equations in matrix form if I'm given this

x'(t) = m1(y(t) − x(t)) = −m1x(t) + m1y(t)

y'(t) = m2(x(t) − y(t)) = m2x(t) − m2y(t)

I'm given that m1 = 0.1 and m2 = 0.2

like I know how to do normal matrices alright, but I'm a bit confused what to do since I have 2 equal signs

am I just supposed to break it in half and make both parts equal to the x'(t) and y'(t)?

[wintry steppe]

Can someone help me? I need to convert the Airy differential equation to Bessel equation

Hi I posted a question

#help-11

[spare widget]

I saw the following in a paper

A matrix A is given, and they construct a matrix Z that spans its null-space

Then they claim that the projection of a vector on the null space of A is given by:

Z(Z^TZ)^{-1}Z^T

this I could reverse engineer from

$\min_x|Zx - y|^2 \implies x = (Z^TZ)^{-1}Z^Ty$

[stoic python]

criver

[spare widget]

so they want the closest vector Zx to y, and that is why the projection is Z(Z^TZ)^{-1}Z^T - I get this part

Then they claim that I-A^T(AA^T)^{-1}A = Z(Z^TZ)^{-1}Z

and I am not sure how they come to this conclusion

as far as I can tell A^T(AA^T)^{-1}A supposedly projects on A^T, that is, it tries to find the best approximation A^Tz to some vector w

then with the identity and the subtraction, we take away that part

As I understand it given a vector w

$w_{\parallel A^T} = A\min_{z}|A^Tz-w|^2,, w_{\perp A^T} = w - w_{\parallel A^T}$

[stoic python]

criver

[lavish jewel]

importantly, these are orthogonal projections

that should be all you need

[spare widget]

and the claim is that w_{perp A^T} = w_{parallel Z}

Z is the nullspace of A though, so what is A^T doing there

[zinc timber]

pinv(A) gives the projection onto A and pinv(Z) gives projection onto orthogonal subspace of A

as edd said, they are orthogonal

[lavish jewel]

if you do the SVD of that mess, you get an orthogonal projection VV^T

and then I - VV^T projects onto the ortho comp of the span of V

[spare widget]

yes but why is it A^T paired with Z instead of A paired with Z

[tired fossil]

hey guys, i have a question, for this, how do i find the basis for ker T? do i do each transformation individually?

[zinc timber]

for that you need to find the kerT first

take any arbitrary polynomial a(1-x)+b(1+x)+c(1-x²) and check when T(p)=0

[lavish jewel]

probably wanna convince yourself that the given polynomials are a basis for all polys of order <= 2 first

[zinc timber]

I thought of writing a+bx+cx² but then I thought nah, OP can do it

[spare widget]

ok, yeah the nullspace of A is orthogonal to the row space A^T

[lavish jewel]

might wanna look up fundamental theorem of linalg

the SVD does quick work of these properties

[spare widget]

yeah I have even had to prove that

[lavish jewel]

(that's kinda circular)

[spare widget]

brain for some reason doesn't turn on though unless I have solved enough problems with it

[tired fossil]

so wait, i take an arbitrary polynonmial first?

[spare widget]

What happens though if AA^T is singular? I am assuming I would have to compute its eigendecomposition and take the pseudo-inverse in the sense of \lambda_i' = 1/\lambda_i for lambda_i !=0, and \lambda_i' = 0 for lambda_i = 0.

this projection seems to rely on the existence on the inverse in: A^T(AA^T)^{-1}A

[lavish jewel]

you actually WANT that to be singular

otherwise the projection is an identity matrix and its complement is a 0 matrix, and that's trivial

indeed you use the pseudo inverse

[spare widget]

I am talking about: AA^T

[lavish jewel]

yes

[spare widget]

if it's singular then I - A^T(AA^T)^{-1}A is ill-defined

[lavish jewel]

you use the pseudo inverse

[zinc timber]

there's a fundamental theorem of linalg?

[spare widget]

strang

[lavish jewel]

it's the name made popular by strang

[zinc timber]

which one?

[spare widget]

https://www.engineering.iastate.edu/~julied/classes/CE570/Notes/strangpaper.pdf

[lavish jewel]

the relationship among col space, left null space, null space, and row space

[zinc timber]

nice

[spare widget]

that doesn't sound right, I am fairly sure that what I have is non-singular for most cases, unless I set contradictory constraints

A is mxn with full row-rank

[lavish jewel]

then the null space is just the 0 vector and you don't have to worry

[spare widget]

the issue is I want to feed it contradictory constraints and satisfy those in an L2 sense

[lavish jewel]

what is "contradictory constraints"

[spare widget]

e.g. introducing linearly dependent rows

Ax = b

where A has been supplemented with linearly dependent rows

the usual A is # rows < # cols and linearly independent rows

then AA^T is non-singular

however if I supplement linearly dependent rows, then AA^T is singular

[lavish jewel]

where does the word "contradictory" come from though

[spare widget]

A is a constraint matrix in my case, but that's probably not very relevant, contradictory constraints are linearly dependent

u_i = b1 and u_i = b2 with b1!=b2

[lavish jewel]

that makes the rows linearly independent

[spare widget]

the standard setting where you have this is linear least squares

[lavish jewel]

(if you're looking at the augmented mat)

[spare widget]

but there A^TA is non-singular

in my case both AA^T and A^TA become singular

[lavish jewel]

that's fine

[spare widget]

yes

[lavish jewel]

wdym yes, i'm saying the opposite as you

[spare widget]

My understanding is that then the pseudo-inverse would require me to do an eigendecomposition

but I would like to avoid that

basically is there any way to rewrite this to be non-singular

[lavish jewel]

no

the whole point of this is that in some cases there is no exact sol, and in others there are infinitely many

[spare widget]

that I understand but I want to apply this for the aformentioned projection

I am guessing the infinitely many solutions problem is reduced by requiring that the initial "free" components remain untouched

[lavish jewel]

you can add in regularization as you see fit

[spare widget]

which I think is exactly what the pseudoinverse through the eigendecomposition would do

[lavish jewel]

it depends

when there are infinitely many sols, you get a projection onto the row space

and well, in the other case as well

this corresponds to a minimum norm solution

(2-norm)

[spare widget]

yes it's a L2 norm minimum solution

[tired fossil]

sorry, but i never understtod what you said, so, this is what i have

[spare widget]

Basically it's the standard least squares, but if you have introduced linearly dependent columns in there, making for example A^TA singular

how do people deal with this in practice?

[lavish jewel]

use a pseudo inv

[tired fossil]

Is this what I am supposed to start with?

[spare widget]

eigendecomposition for large matrices is expensive

I usually use a CG solver, but I am worried about the matrix being singular in this case

[lavish jewel]

if you mean in general in practice, if you can't afford to compute the eigendecomp, you use an iterative procedure of your choice

gradient methods, (quasi) newton methods, with or without regularizers

or something heuristic/data driven

in this case you rely on regularization to find the solution you want

[tired fossil]

can anyone help me by any chance?

this is my question, i just dont know how to find a basis in here.

[spare widget]

so I am guessing the issue arises from the fact that neither the rows nor the columns are linearly independent. While in the standard case if the rows are linearly dependent one uses A^TA instead, and if the columns are linearly dependent then AA^T.

[lavish jewel]

seb, you are looking for scalars a,b,c, so that T{av1 + bv2 + cv3} = aT{v1} + bT{v2} + cT{v3} = [0,0;0,0]

where v1 = (1-x), v2 = (1+x), v3 = (1-x^2)

[lavish jewel]

in general you really don't want to use the gramian unless you have good reasons to

these matrices have a really bad condition number

so you'd need preconditioning or very stable algorithms. you'd also need some way to accelerate convergence

[spare widget]

the reason is that I need a least squares solution, because the constraints are conflicting

I am aware that the condition number is squared

I just haven't come up with anything better

[lavish jewel]

what i mean is that you can solve || Ax - y || without relying on a system involving AA^T

[spare widget]

how?

[lavish jewel]

it still shows up implicitly in some algs, but can be circumvented

[spare widget]

you get A^TAx = A^Ty from setting grad = 0

as far as I know one cannot escape this

to be sure, I do not apply CG on A^TAx = A^Ty

I use CGNR, which is stabilized for the normal equations

it's just that I am used to working with A^TA positive definite, and now it's positive semi-definite

albeit I just found some papers that the algorithm supposedly converges even in that case

[lavish jewel]

you could use gradient-free methods

[spare widget]

you mean direct solvers? those cannot handle the matrix sizes I am working with

[lavish jewel]

i don't mean direct solvers

stuff like coordinate descent, for example, only relies on per-variable derivatives. instead of dealing with a gramian that pops up when looking at the gradient, you instead deal with 2-norms of columns of the matrix A

there's also stuff like sim. annealing and whatnot

[spare widget]

I haven't looked at coordinate descent, but sounds like gradients per coordinate, as far as simulated annealing goes - I have done that for other problems, it's extremely slow (compared to methods that rely on gradient information)

[lavish jewel]

it shouldn't really be much slower

gradient desc. is very slow

[spare widget]

I just need to think over what this means geometrically, because there should certainly be a way to simplify this in order to get a non-singular matrix inversion

e.g. somehow removing the null-space out

[lavish jewel]

well if you find it, do publish it in a paper

[spare widget]

it's probably been done already and I just can't find it

or it's probably too trivial to deserve a paper

[lavish jewel]

you can compute the SVD by doing row reduction twice btw

it's not SUPER expensive

you would only have trouble if the matrix is humongous

e.g. can't fit in memory

[spare widget]

it is humongous and sparse

I gave up on anything non-iterative a while ago

even LDL^T Cholesky breaks on it

the incomplete one too

[lavish jewel]

breaks in what sense

[spare widget]

as in D_ii < 0 for some i, that is, numerical precision

and that's with double precision

[lavish jewel]

oh well

[spare widget]

It's alright I'll figure something out, CGNR is supposed to work

[lavish jewel]

at any rate, what you were asking for doesn't exist

you can solve a different problem that gives the same solution, but you can't rewrite it in terms of full rank stuff

[spare widget]

I just wanted to figure out something theoretical, but while discussing with you I realized that having both rows and columns linearly dependent poses quite a few issues

[lavish jewel]

since the crux of the problem is precisely that the matrix is not full rank

[spare widget]

The problem has a unique solution definitely, I just have to figure out what that translates into algebraically, since I actually want only one solution out of the infinitely many, I just need to be more careful with the modeling.

[lavish jewel]

your matrix A has full column rank?

[spare widget]

no that's the problem

the matrix A has full row rank if there are no conflicting constraints

[lavish jewel]

then it does not have a unique solution

[spare widget]

then it's trivial and one just does AA^T

[lavish jewel]

😛 be careful with the wording

[spare widget]

but when I add conflicting constraints

[lavish jewel]

if you want a specific one, the only way is to add a regularization term

[spare widget]

then I want those to be satisfied in a least squares sense

so my guess is that theoretically the conflicting constraints could be taken out and turned into a single one

and then I'll get a full row-rank matrix

[lavish jewel]

you can do this with lagrange multipliers, sure

like adding a slack variable

[spare widget]

e.g. if I I know that row 1,3,5 are linearly dependent, I could take them out, and apply A^TA for those - scratch that, I basically need to turn them into a single constraint that satisfies the 3 in some least square sense

[lavish jewel]

but now you have to exactly solve for this variable too

[spare widget]

Lagrange multipliers require non-conflicting constraints

[lavish jewel]

i'm sorry, your nomenclature is throwing me off

what i mean is adding extra variables and requiring them to be positive, for example

[spare widget]

Lagrange multipliers require linearly independent rows in the constraint matrix Ax = b

[lavish jewel]

and using lagrange mults for these new constraints

Ax = b is normally called the cost or objective, not constraint

if it were a constraint, the answer to your question formally is "the feasible set is empty"

and you're done

[spare widget]

$\min_x f(x), \quad \text{s.t.} Ax = b$

[stoic python]

criver

[spare widget]

A is the constraints matrix

if f(x) = 1/2x^TQx for example

then one gets

[lavish jewel]

then this means there is no solution

[spare widget]

$\begin{bmatrix} Q & A^T \ A & 0 \end{bmatrix} \begin{bmatrix} x \ \lambda\end{bmatrix} = \begin{bmatrix} 0 \ b \end{bmatrix}$

[stoic python]

criver

[spare widget]

yes the system is inconsistent, instead I replace it with ||Ax - b||^2

the standard way to solve this is A^TAx = A^Tb, except A^TA is singular in this case (as it should be in order to have some interesting feasibility set)

[spare widget]

it's a way to satisfy the constraints in a weak sense (L2)

it's equivalent to the standard approach for non-conflicting constraints

[lavish jewel]

so you mean $\min_x f(x) ,,s.t. ,, \Vert Ax - y \Vert_2^2 < \epsilon$

[stoic python]

Edd

[spare widget]

$\min_x x^TQx, \quad \text{s.t.} \min_{x}|Ax-y|^2$

[stoic python]

criver

[spare widget]

I am not sure how to formulate it properly

[lavish jewel]

the way i wrote it

[spare widget]

the constraints are more important than f(x)

[lavish jewel]

there's no "more important"

[spare widget]

in the sense that

if they were non-conflicting

then it would be Ax = b

the minimisation for the constraints is only to break up contradictions there

once this is done the x is "fixed"

e.g. you can reformulate

$min_x x^TQx, \text{s.t.} Ax = b \implies \\min_y y^TZ^TQZy = -Z^TQA^T(AA^T)^{-1}b$

where Z is the null space of A

[stoic python]

criver

[spare widget]

so you can even rewrite it without any constraints - i.e. they can be factored out before the whole thing, since they are enforced strongly

Either way, this is probably too technical

[lavish jewel]

seems pretty straightforward

if you want to avoid those (pseudo)inverses, the whole problem can be written as a problem with a symmetric psd mat

[spare widget]

baiscally I know a unique minimizer exists

[lavish jewel]

if Q has full rank, yes

the problem is strictly convex

[spare widget]

yes, but I replace Ax = b with min_x|Ax-b|^2

I can actually give a simple example

imagine a^T x = b is one constraint

[lavish jewel]

you don't have to, it's been clear for like 1hr lol

[spare widget]

the null-space is of dimension (n-1)

now I can add a conflicting constraint

[queen geode]

Uh anybody can tell me why Im not getting the same result using Sarrus as what symbolab or wolfram is outputing?

[spare widget]

a^Tx = b, a^Tx = c, the null-space is still (n-1), and I want the x to "satisfy" the above in a least square sense

except the matrix (AA^T) is singular in that case (since the same row repeats two times)

[queen geode]

This is what I get, but symbolab outputs 4 instead of 18

4 makes it actually solvable, 18 doesnt

Uh all the x in there are me being dumb and forgetting its lambda

And not x

[spare widget]

A thing that would make the matrix non-singular is substituting those two constraints with a single one, e.g. a^Tx = d, such that it minimise (a^Tx-b)^2 + (a^Tx-c)^2. I think I just have to involve Z somewhere in there to reduce this to a non-singular system.

Yeah, I think I figured it out while trying to explain it

I just have to decompose x = Vx_A + Zx_z, such that AZ = 0, and V has independent columns ([V Z] should span R^n). Then Ax = AVx_A = b and (AV)^T(AV) is non-singular

So I just need to solve ||Ax-b||^2 in the space orthogonal to the null-space of A

my mistake was picking V = A^T, which works in the case where A has linearly independent rows, but doesn't otherwise

[lavish jewel]

that's indeed the classical solution to the problem

you can use an iterative alg to build a basis for the null space

[spare widget]

I haven't though yet about the algorithm part

I am happy I finally figured out what I was doing wrong theoretically though

[lavish jewel]

i forget the name for this

something along the lines of generalized beamforming in the sigproc community

[spare widget]

If possible I wanted to avoid building the basis, that's why I was looking at I-VV^ instead of VV^T

[spare widget]

Lmao wat

[lavish jewel]

it shows up in papers from like 50 years ago

[spare widget]

Gmres?

[lavish jewel]

hmm?

[spare widget]

gmres builds a basis, which is why I avoid it, because I don't want to carry the vectors around with me

[lavish jewel]

i meant your whole problem, cost func and constraints

[spare widget]

afaik that's just quadratic programming, albeit they do not introduce conflicting constraints usually

standard optimization books have the non conflicting version

[lavish jewel]

if you want to do it this way, anyway, you need a basis for the image or the null space

[zinc timber]

you guys are still talking about optimization

[lavish jewel]

otherwise, use lagrange on the form with epsilon

your form also shows up in opt books lol

[spare widget]

They were avoiding doing so in the nonconflicting case through the I - A^T(AA^T)^{-1}A

[zinc timber]

if it's a QPP then yes, I hated solving those

[spare widget]

The conflicting thing? Please do tell so I can read up on this

[lavish jewel]

just look up convex up