Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

0
votes
1answer
78 views

Stability analysis of Numerical Method

For a system of ODEs, I'm looking at the case where $$u'=Au$$ where $A$ is diagonalisable so $$u'=R\Lambda R^{-1}u.$$ In the notes I am looking at it goes on to say we can premultiply by $R^{-1}$ so ...
1
vote
1answer
124 views

Does a Convex Function need to be Continuous

I have been trying the following problem and I am very confused. If possible the problem should be solved with derivatives. If the derivative exists for all the points on the graph then it is ...
0
votes
2answers
642 views

Quadratic Function must be positive definite to have a unique minimum

I have attempted the following question multiple times and I am very confused about the proof please help me solve it. Let $V(x)=a+b^{T}x+\frac{1}{2}x^{T}Cx$ for some $a \in \mathbb{R}, b \in ...
2
votes
2answers
710 views

Power iteration sign of eigenvalue?

I need to write a program which computes all eigenvalues and corresponding eigenvectors. I'd like to use power iterations method (I know that it's not good but it's really necessary). my algorithm ...
0
votes
1answer
105 views

spectral radius of matrix with elements less than one

Assume we have a square matrix A whose elemnts are less than 1, Can we say that its spectral radius is also less than 1. Can we say that the absolute value of its eigenvalues are also less than 1?
3
votes
3answers
707 views

Demonstrate that a matrix has no LU factorization

Have to show that $$\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}$$ has no LU factorization. It seems trivial just to say that this cannot have an LU decomposition because it is a lower ...
2
votes
2answers
118 views

eigenvalues for symmetric and non-symmetric matrices

I know the Power methods and Jacobi methods are suitable to finding eigenvalues for symmetric matrices, please tell me other methods for this matrices. And what are the methods for the Non-symmetric ...
0
votes
1answer
109 views

Impossible Schur Factorizations

I am having trouble finding the schur factorization of the following matrix: $A=\begin{pmatrix}3&8 \\ -2&3 \end{pmatrix}$ I followed an algorithm in the book, as well as computing an answer ...
1
vote
1answer
308 views

Minimizing the Determinant

I would like to minimize the determinant of the following matrix, det(A) $A = (VV^T+\lambda I)^{-1}$ and $\lambda$ is set to be very small.
0
votes
1answer
108 views

Fast Gauss-Seidel convergence on low rank matrices

I stumbled upon the following remarkable fact when experimenting with the Gauss-Seidel iterative solver: First I construct a low-rank symmetric positive semi-definite matrix $A = M^TM$ with M a ...
3
votes
1answer
104 views

Prove this matrix is invertible for $n < m-1$

Prove this $(n+1)\times (n+1)$ matrix $\bf{A}$ is invertible for $n < m-1$ and the $x_k$ distinct, \begin{bmatrix} m &\sum_{k=1}^mx_k &\sum_{k=1}^mx_k^2 &\cdots ...
0
votes
1answer
206 views

Completeness of eigenvectors of Hermitian Matrix.

How do you show that eigenvectors of a Hermitian matrix form a complete set of basis?
3
votes
1answer
258 views

condition number after scaling matrix

Maybe a well-known question. Let $\Sigma$ represent a real symmetric positive definite matrix, i.e. a covariance matrix. Which diagonal matrix $D$ with positive diagonal minimizes the condition ...
0
votes
1answer
32 views

Proving the equality: $D^{-1}+D^{-1}CPBD^{-1}=(D-CA^{-1}B)^{-1}$ where $P=(A-BD^{-1}C)^{-1}$

I am trying to prove the following equality that I need to use as an intermediate step to solve one of my problems. The equality is the following: $D^{-1}+D^{-1}CPBD^{-1}=(D-CA^{-1}B)^{-1}$, where ...
0
votes
1answer
93 views

Dense symmetric positive definite matrix

How could one define a dense symmetric positive definite matrix (dimension $1000 \times 1000$) with uniformly distributed eigenvalues (with the smallest eigenvalue $1$ and the condition number $100$) ...
2
votes
0answers
53 views

linear algebra formulation help

I asked this on mathoverflow as well and apologies for cross-posting. I am trying to compute this so-called bending energy matrix. The bending energy of a thin plate in 3D is given by: $$ BE = ...
2
votes
1answer
206 views

Help in this exercise about Richardson extrapolation.

We know $F(h)=a_0 +a_1h + a_2 h^3$ $F(1)=4$; $F(1/2)=21/8$; $F(1/4)=145/64$ Find a approximation of $F(0)=a_0$ with Richardson extrapolation method with an absolute error less than $10^{-2}.$ ...
0
votes
1answer
28 views

If $λ_i > 0, \forall i$, $A$ is positive definite

Given that $A \in R^{n,n}$, $λ_i $ the eigenvalues and $x_i$ the eigenvectors ($x_i^Tx_j=δ_{ij}$). I have to show that if $λ_i > 0, \forall i$, $A$ is positive definite. My idea is the following: ...
1
vote
0answers
192 views

Proof-finding: Power iteration and complexity of the Rayleigh quotient

I'm searching for a proof for this theorem: \begin{align} |\lambda^{(k)}-\lambda_1| = \mathcal{O}\Big(\Big|\frac{\lambda_2}{\lambda_1}\Big|^{2k}\Big) \end{align} where \begin{align} \lambda^{(k)} ...
4
votes
4answers
608 views

How to find 2x2 matrix with non zero elements and repeated eigenvalues?

I need to find a 2x2 matrix with non zero elements that has eigenvalue = 1 repeated (double). How can i do that? Thanks!
1
vote
1answer
221 views

Computing the best-fit plane normal from n points

I've been working steadily through "3D Math Primer for Graphics and Game Development" and am stuck on how the authors derived their equation for the best-fit plane normal given n points. Please note, ...
3
votes
0answers
163 views

Difference between Householder Reflections and Gram-Schmidt?

In numerical QR decomposition, when we calculate the orthonormal factor Q of a matrix, what is the difference in results if we use Householder Reflections to normalize the matrix or use Gram-Schmidt ...
1
vote
2answers
68 views

Can you compute rank r factorization of a n*n matrix in time O(n^2 r)?

I am wondering if you can compute the SVD/eigenvectors of a rank r matrix of size n*n in time O(n^2 r)? My understanding is that standard eigenvector computations involve bringing matrix into ...
0
votes
2answers
59 views

How to understand or show this?

We have $$F=ABh^{p_1}+\theta (h^{p_2})$$ $$G=Ah^{p_1}+\theta (h^{p_2})$$ We $A$,$B$ are real numbers, $h$ positive, $|h|\leq 1$ , $p_1<p_2$ natural numbers and $\theta(h)$ means that it is of ...
0
votes
1answer
91 views

Rate of Convergence of Generalized Iterative Method

Consider the generalized iterative method for finding polynomial roots: $z_{k+1}=z_k +d\frac{(1/p)^{(d-1)}(z_k)}{(1/p)^{(d)}(z_k)}$ where d is a positive integer. Note that Newton's Method is a ...
2
votes
3answers
130 views

properties of positive definite matrix

If $A$ is a symmetric positive definite matrix can we conclude $A^{n}$ is positive define too? Why? For example for $n=2$: $x^{T}(AA)x=x^{T}(AA^{T})x=(x^{T}A)^2>0$; for $n>2$?
0
votes
1answer
47 views

function of matrix and eigen values

I want to calculate exp(A), A is matrix, with numann series. is this series depend of matrix's eigen values? for example if it's eigen values are large, is numann series useful for this function?
0
votes
1answer
95 views

Differences between methods for solving linear equation system

I have a huge linear equation system in this form: F=K.Δ as usual form of problems in the finite element method, where the F vector and K are known and Δ vector is unknown. There are several ...
1
vote
1answer
212 views

Need matlab help to construct a numerical example for solving system of linear equation for random matrices

I am reading this paper(page 183). In this paper the iterative methods for computing some solution of the general restricted linear equations \begin{eqnarray} Ax = b, ~~~~ x\in R(A^{k})~~~~ b\in ...
1
vote
1answer
85 views

Most efficient way to find distinct complementary subspaces over a finite field

Let $V$ be a $n$-dimensional vector space over $\mathbb{F}_p$ and let $W$ be a $k$-dimensional subspace. What's the most efficient way to algorithmically write down a basis for each distinct subspace ...
4
votes
1answer
103 views

Understanding higher order SVD

Can someone explain the singular value decomposition of a tensor (maybe a 3 dimensional matrix) with an example? It is intuitively difficult to the get the meaning from just the formulas. On a ...
0
votes
2answers
99 views

A linear programming to obtain “canonical basis of convex cone”

In my research a I need to solve the linear equation (getting its null space) under some constraints. The matrix is given below: The constraints shall be (x1...x[16]>0, x[17]...x[20] arbitary...) ...
1
vote
1answer
84 views

Proof involving Gauss–Seidel method.

I've got a symmetric positive definite matrix $A$ that I decompose into $A=U+R$ where $U$ is the upper triangular portion of $A$ including the diagonal and $R$ is $A-U$. I've shown that $$x^TAx = ...
-1
votes
1answer
41 views

Find the equation to movement with a middle point locked

I have this scenario: One particle has to go from $0$ point to $y$ point in $1$ sec. The particle needs to start moving at time $0$ ($time=0sec$), and to go accelerating until the middle of time ...
1
vote
1answer
80 views

a conjugate gradients result for eigenvalue estimates

Consider the not preconditioned CG-method for a linear system $Ax=b$. Define $\beta_j = \frac{(r_{j+1},r_{j+1})}{(r_j,r_j)}$ and $\alpha_j=\frac{(r_j,r_j)}{(Ap_j,p_j)}$, where $(x,y) = y^Tx$ denotes ...
4
votes
1answer
1k views

What is the time complexity of conjugate gradient method

I have been trying to figure our the time complexity of conjugate gradient method I have to solve a system of linear equations given by $$ Ax=b $$ where A is sparse and positive definite symmetrix ...
1
vote
1answer
62 views

Conditioning considerations in least square solutions via the normal equations

I'm a little unsure about how to classify conditioning issues with solving least squares equations via the normal equations approach. I'm hoping to get verification that what I say below is correct, ...
3
votes
1answer
88 views

Solve Ax = b, but I have a function that implements A

I have an overdetermined linear system $Ax = b$. I need to choose an $x$. $x$ has about 100 elements in it. If I had the matrix $A$, I would set x equal $A^\dagger b$, the pseudoinverse of $A$ ...
1
vote
1answer
344 views

cube root of positive definite matrix

Suppose that $A$ is a real symmetric positive definite $20\times 20$ matrix with condition number $\kappa\le 1000$. I want to solve the system of linear equations $$A^{1/3}x=b$$ with $10$-digit ...
1
vote
0answers
84 views

Solving for A in the system Ax = 0

Consider the system of linear equations $A x = 0$ where $A$ is a $K \times M$ matrix of reals and $x$ is an $M \times 1$ vector of reals. The matrix $A$ is unknown but we can generate $x$s that ...
0
votes
0answers
35 views

only calculate diagonal of cholesky decomposition

I have a massive matrix $A$ that I can't hold entirely in memory, but it is possible to easily calculate individual entries ($A(i,j)$). I'm only interested in calculating the diagonal entries of the ...
1
vote
0answers
36 views

The least-squares solution for interval data

I would like to solve the least-squares for $\mathbf{Ax} = \mathbf{y}$ with some values in $\mathbf{A}$ and also in $\mathbf{y}$ are interval-valued numbers. In a more detail, e.g.,: $$ ...
1
vote
4answers
127 views

Proof $\langle Ax,y\rangle = \langle x,A^*y\rangle$ when $A$ Hermitian

I was trying to understand a proof of why a Hermitian $A$ matrix has its eigenvectors orthogonal. As part of the proof they state $$\langle Ax,y\rangle = \langle x,A^*y\rangle$$ From which property ...
1
vote
0answers
292 views

Solving linear system of equations using Successive Over-Relaxation

I was solving a system of linear equations with SOR. I used different values of relaxation factor (w) for the different runs. I found that for all w > w' (1 < w' < 2), the error is the result ...
1
vote
0answers
223 views

Orthogonal Procrustes Problem

The classical orthogonal Procrustes problem concerns finding the matrix $\Omega$ which minimizes $||A\Omega-B||_{F}$ subject to $\Omega'\Omega=I$, with A and B known matrices. Let A be the identity. I ...
1
vote
1answer
235 views

Solving Poisson Equation Finite-difference using maple

How do I solving Poisson Equation Finite-difference using maple consider Poisson equation $$\frac{\partial^2u}{\partial x^2} (x,y)+ \frac{\partial^2u}{\partial y^2} (x,y) = x*e^y$$ $0<x<2$ ...
5
votes
1answer
179 views

QR factorization of a special structured matrix

A friend asked me the following interesting question: Let $$A = \begin{bmatrix} R \\ \xi{\rm I} \end{bmatrix},$$ where $R \in \mathbb{R}^{n \times n}$ is an upper triangular and ${\rm ...
0
votes
1answer
21 views

Are Similar Matrices and Unitary Property related?

Recall that 2 matrices $A, B\in R^{n,n}$ are similar if there exists a matrix $P$ such that $A=P^{-1}BP$. In this case is $P$ always orthogonal?
0
votes
1answer
91 views

Find upper Hessenberg by Householder transformation

I have a matrix that looks like this: $$ \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \epsilon & 0 & 0 & 0 \\ ...
2
votes
1answer
99 views

Show that every operator norm is consistent

Is the following a correct way to show that operator norms are consistent? $$ \|AB\|=\max_{Bx \ne 0}\frac{\|ABx\|_\alpha }{\|x\|_\alpha} =\max_{ Bx\ne 0}\frac{\|ABx\|_\alpha}{\|Bx\|_\alpha} ...