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

learn more… | top users | synonyms

0
votes
2answers
14 views

What is the computational cost of reduced row echelon and finding the null space?

I'm taking computational linear algebra, and haven't been able to find too much information about the computational cost (in terms of m=rows and n=cols) of these two routines: Reduced Row Echelon ...
0
votes
1answer
28 views

The equivalence of numerical radius and spectral norm

Let $A$ be a $n\times n$ complex matrix. Define the numerical norm of $A$ as $$w(A)=\sup\{|x^*Ax|;\|x\|_2=1\}, \|x\|_2^2=\sum_{i=1}^n|x_i|^2.$$ And the spectral norm of $A$ is $$\|A\|_\infty ...
0
votes
1answer
8 views

What is and what represents a convergents function in polynomial form?

$$\mathbf{convergents}(cos(1), 20)$$ What exactly is a convergents function and what, that series of fractions is representing ? There is an use for this in numerical linear algebra ? Feel free to ...
0
votes
0answers
21 views

Optimized way to compute L1 distance matrix

I'm computing distances between two groups of multi-dimensional points giving a matrix of distances pairwise between points. For the L2 (euclidean) distance I can use optimized matrix multiplication ...
0
votes
2answers
20 views

Creating a random square matrix with known singular values

The first step in one question has me creating a random square matrix A with singular values given as $2^{-1}, 2^{-2}\dots 2^{-n}$. There is no other information about what assumptions can be made ...
1
vote
0answers
40 views

Does this function have a unique fixed point?

Consider the following equations in fixed-point form: $$\mathbf{x}=F(\mathbf{x})=[f_1(\mathbf{x}),f_2(\mathbf{x}),\cdots,f_n(\mathbf{x})]^T$$ where the function $f_i$ is defined as ...
1
vote
0answers
8 views

Speed of pseudo-inverse (with possibly ill-conditioned matrices)

I am computing the pseudo-inverse of several matrices of identical size $m \times n$ . However, computation (e.g. with the LAPACK pinv) seems to be much slower in some cases (5 to 10 times slower). ...
-1
votes
1answer
56 views

Invent a linear mapping given the following conditions. [on hold]

Invent a linear mapping L such that: $L(1,2)=(3,5)$ and $L(-2,1)=(2,-3)$ I'm just unsure on how to start this problem, if anyone can give me any tips that be great thanks!
0
votes
1answer
23 views

An Inequality in Numerical Optimization

I am reading Jorge Nocedal and Sepher J. Wright's Numerical Optimization and stuck at an exercise 4.6 in chapter 4. The Canchy-Schwarz inequality states that for any vector $u$ and $v$, we have ...
-2
votes
1answer
36 views

Domain/codmain + range/kernel for linear mappings [on hold]

Consider the linear mapping: $$L(x_1,x_2)=(2x_1-3x_2,4x_1+5x_2,2x_1-x_2)$$ Solve for: (a) Domain and codomain of L (b) Standard matrix of L (c) Basis for the range of L (d) Basis for the kernel ...
2
votes
1answer
47 views

about the power of a matrix

Assume that matrix $A$ contains only 0 or 1 elements. Could anyone give me some condition, under which the matrices $A^i$ (for $i=1,2,3,...,k$) still contains only 0 or 1 elements. For example, I ...
1
vote
1answer
48 views

Solve quadric equation system

How to solve this? For given real and symetric matrices $A_1,A_2,A_3,A_4\in\mathbb{R}^{4\times4}$ find $x\in\mathbb{R}^4$ $$x^TA_1x=0$$ $$x^TA_2x=0$$ $$x^TA_3x=0$$ $$x^TA_4x=0$$
8
votes
2answers
247 views

Interpolation polynomial Challenge

suppose $p(x)=x^k-x^t, k \neq t $ (k,t is a positive integer). function q(x) be a Interpolation polynomial from degree lower or equal n, to data $i=1,...,n+1, (x_i ,p(x_i))$. if ----------- then ...
1
vote
0answers
29 views

Strictly diagonal matrix

Suppose that matrix $A$ is strictly diagonally dominant, show that $||A^{-1}||_{\infty}\leq[min(|a_{ii}|-|\sum_{i\neq j}^n a_{ij}|)]^{-1}$.
0
votes
0answers
24 views

Proof the described sequence obey the formula

The sequence start by solving algebraic equation $ P_1V_1^{1.4}=P_2(V_1-\frac{a}{n})^{1.4} $ for P2 and substitute value of $ P_2$ into next equation $P_2(V_1-\frac{a}{n})=P_3(V_1+\frac{a}{n})$. ...
1
vote
1answer
31 views

Condition number - proof

I have a problem with which I've been struggling for a while. It's probably not that difficult, but I seem to be stuck so... here we are. Let A be an invertible lower- or upper-triangular matrix ...
0
votes
0answers
28 views

Saddle point problem (KKT) with block-diagonal matrix

Consider the following saddle point problem originating from an interior-point method algorithm: $$ \begin{bmatrix}\mathbf{H} & \mathbf{A}^{T}\\ \mathbf{A} & \mathbf{0} ...
0
votes
2answers
30 views

Euler method(path s1s2=s2s1)

Given a differential equation $\frac{dy}{dx}=f(x,y(x)), y(x_0)=y_0$. What is the condition for function of f(x,y) such that the result of $y(x_0+S_1+S_2)$ by using Euler forward method, a step size ...
0
votes
1answer
30 views

How do I find transformation matrix with respect to given basis in the domain and/or the codomain, given the transformation in the standard basis?

I´m being given a linear transformation, for which I can find the standard basis in the domain and codomain; but then, the book ask to find the associated matrix related to a new basis for the ...
0
votes
1answer
35 views

An algorithm of solving a non-homogeneous linear equation by random matrices

I'm looking for the proof of the following numerical algorithm. Suppose I want to solve a non-homogeneous linear equation \begin{equation} A x = b \end{equation} The matrix $A$ is non-invertible and ...
0
votes
1answer
40 views

Is it possible to optimize solution of this linear system?

I have a matrix of the form: ...
1
vote
2answers
78 views

How to prove the eigenvalues of tridiagonal matrix?

Assume the tridiagonal matrix $T$ is in this form: $$ T = \begin{bmatrix} a & c & & & &\\ b & a & c & ...
0
votes
0answers
31 views

matrix diagonalization without eigen decomposition, what other ways available?

I have a matrix, $A$ (it may be symmetric or asymmetric). I need to have a diagonal matrix without eigenvalue decomposition, please suggest what others ways are possible? Any new idea would be much ...
1
vote
2answers
32 views

Finding only first row in a matrix inverse

Let's say I have a somewhat large matrix $M$ and I need to find its inverse $M^{-1}$, but I only care about the first row in that inverse, what's the best algorithm to use to calculate just this row? ...
1
vote
0answers
19 views

Solve set of poorly conditioned linear equations in block matrix form

I would like to solve the following set of linear equations where A, B, C and D are each 4x4 matrices. K is then an 8x8 matrix The values in A and D have magnitudes of $\approx 10^{17}$, B has ...
1
vote
0answers
24 views

Write down a linear programming problem

I want to replicate a linear programming problem.I have the following information, for the background." A fuzzy regression analysis with only one independent variable X results in the following ...
2
votes
0answers
31 views

Lagrange multiplier for more than one constraints.

How to minimize $x^TAx$ over the set $D=(x\geq 0, x^TBx=1$ and $(I-A^\dagger A)x=0$), where $A$ is copositive matrix of order $n-1$ and $B$ is strictly copositive matrix of order $n$. If I drop the ...
0
votes
1answer
10 views

R3 to Planar Subspace Tranform

I'll ask my question three ways to try to maximize my chances of successful communication. I have: a point 'P' in R3 with coordinates $(P_X,P_Y,P_Z)$ A plane Defined by: A point 'O' given by ...
1
vote
0answers
28 views

Solve linear system with matlab

In my problem, $A$ is a $m \times n$ matrix with $m \geq n$ and $\mathrm{rank}(A)= n$. Let $\Gamma$ be the $(m+n) \times n$ matrix defined by : $$ \Gamma = \begin{bmatrix} A \\ \mathrm{I_{n}} ...
3
votes
1answer
42 views

Generalized inverse/Pseudo Inverse

Let $A_{m. n}$ be a matrix with rank $p$ where $p\leq m$ and $p\leq n$. First Question: We need to show that $A$ can be decomposed as a product of two matrices $A=BC$ where $B$ is an $m$ by $p$ and ...
0
votes
0answers
20 views

computing leftmost eigenpair of positive-definite matrix

Let $A$ be an $n\times n$ real symmetric positive-definite matrix. Assume that $n$ is large and that $A$ is dense (i.e. it is not sparse). Question: What is the state-of-the-art algorithmically for ...
0
votes
0answers
38 views

Test for powers method

I have been told that for a normal matrix $A$, the powers method (i.e. computing the succession of Rayleigh quotients for a succession of vectors $z_k=A\cdot z_{k-1}$) can use the following stop ...
3
votes
1answer
44 views

Inverse of a diagonal matrix plus a constant

I am looking for an efficient solution for inverting a matrix in the following form: $D+aP$ where D is a (full-rank) diagonal matrix, a is a constant, and P is a one matrix. This question Inverse of ...
2
votes
2answers
126 views

How to efficiently solve a series of similar matrix equations using the LU decomposition

This is the problem I'm dealing with: Let $\sigma_1,\dots,\sigma_n \in \mathbb{R}$ and $b_1,\dots,b_n$ be column vectors of length $n$. Consider the system $$ (A - \sigma_jI)x_j = b_j, \quad ...
0
votes
1answer
23 views

Function from one Null space to Another

Suppose a single vector space over $R$ of degree $n$, and two matrices $A, B$ of arbitrary row size, but col size $n$, s.t. their individual null spaces are linear subspaces of this vector space. Is ...
0
votes
0answers
25 views

Are there any sure-fire methods for correctly arranging matricies for Gaussian Elimination?

I am attempting to make a Gaussian Elimination solver for systems of linear equations that contain less than 100 equations. I have roughed out a method for creating and filling in the diagonal of a ...
0
votes
4answers
106 views

Shortest Distance between a Point and a Numerical 2D Curve

I have a 2D Curve. I have all the numerical values for the line within a certain range. I do not have an equation for this line. At several points in this 2D space I want to calculate the shortest ...
0
votes
1answer
27 views

Equation that maps two values to three? [closed]

I'm trying to get an equation for a line in 2-dimensions that maps into an equation for a line in 3-dimensions where $$ f(x,y) => x_1,y_1,z_1 $$ and preferably have a resource that teaches me the ...
0
votes
0answers
19 views

Stuck on condition number derivation of the perturbed equation $(A + \Delta)\tilde{x} = b + \delta_b$

I've almost got what I want. We start with $Ax = b $ and $(A + \Delta)\tilde{x} = b + \delta_b$. What I have then is \begin{align*} \tilde{x} - x &= -A^{-1}\Delta\tilde{x} + A^{-1}\delta_b \\ ...
2
votes
0answers
49 views

compute the bisecting normal hyperplane between two $n$-dimensional points.

I have two points $\mathbf{x_1}$ and $\mathbf{x_2}$, where $\mathbf{x_i}=\{x^i_1, x^i_2, \ldots, x^i_n\}$. I need to find a normal hyperplane $P$ that goes through the midpoint of $\mathbf{x_1}$ and ...
0
votes
1answer
37 views

Jacobi vs. Gauss-Seidel: convergence

I know that for tridiagonal matrices the two iterative methods for linear system solving, the Gauss-Seidel method and the Jacobi one, either both converge or neither converges, and the Gauss-Seidel ...
0
votes
1answer
31 views

Tridiagonalize matrices with Householder transformation

I know that it is possible to tridiagonalize symmetric matrices by using a Householder trafo. I also found that we can get any matrix to Hessenberg form by using Householder trafos, but I still don't ...
0
votes
0answers
34 views

Integration of ODE equation in Matlab / Octave

I have a system of 8 ODE's where the initial conditions are in matrix form. $\frac{dT}{dS} = H T$ where T at the initial state is the identity matrix. $T(a) = I$ H is a constant 8x8 matrix T is ...
0
votes
0answers
16 views

Is the Hessenberg form of a matrix unique?

I have to calculate the Hessenberg form of an matrix using householder reflectors. For real Matrices I get the same result as the 'hess()' function in Matlab, but for Complex Matrices I keep getting ...
0
votes
0answers
57 views

Alternative to the Gram-Schmidt Procedure for Orthogonalization

I was wondering if there is an alternative to the Gram-Schmidt procedure, which instead of being a successive orthogonalization scheme, would be non-successive (simultaneous)? In other words, is there ...
1
vote
1answer
22 views

Matrices admit a QR decomposition

I just wanted to ask which matrices admit a QR decomposition. I think that all matrices $A \in \mathbb{R}^{m \times n}$ with $m \ge n$ admit a QR decomp. Are these the only ones that have a QR decomp, ...
4
votes
1answer
189 views

Generate arbitrary numerically invertable matrix

I'm designing a unit-test for a matrix inversion function. Currently I make a random matrix as a test case by generating its elements with random numbers uniformly distributed in $[0,1)$. If I ...
1
vote
0answers
36 views

stability of FTCS scheme for parabolic equation

Can you suggest any method for stability analysis of FTCS scheme for the the following parabolic equation ? D.E: $u_{t}=a(x,t)u_{xx}+f(x,t,u)$, $0<x<1$, $0<t<T$, $T>0$ BCs: ...
0
votes
0answers
54 views

Proof of theorem about iterative methods

How do I prove that if $A$ is a tridiagonal (or block tridiagonal) matrix then the corresponding $P_J$ and $P_G$ iteration matrices for the Jacobi and Gauss-Seidel methods satisfy that if $\lambda$ is ...
3
votes
1answer
93 views

3-sigma Ellipse, why axis length scales with square root of eigenvalues of covariance-matrix

This is my first post on math.stackexchange and i am not a mathematician, but i took some undergrad math courses and some grad mathematical modelling courses, so i come with a basic understanding of ...