import numpy as np

def qr_gram_schmidt(A):
    """
    Perform QR Decomposition using Gram-Schmidt process.
    :param A: Input matrix (n x m)
    :return: Q (orthogonal matrix), R (upper triangular matrix)
    """
    n, m = A.shape
    Q = np.zeros((n, m))
    R = np.zeros((m, m))

    for j in range(m):
        v = A[:, j]
        for i in range(j):
            R[i, j] = np.dot(Q[:, i], A[:, j])
            v = v - R[i, j] * Q[:, i]
        R[j, j] = np.linalg.norm(v)
        Q[:, j] = v / R[j, j]

    return Q, R

def qr_householder(A):
    """
    Perform QR Decomposition using Householder reflections.
    :param A: Input matrix (n x m)
    :return: Q (orthogonal matrix), R (upper triangular matrix)
    """
    n, m = A.shape
    R = A.copy()
    Q = np.eye(n)

    for k in range(m):
        x = R[k:, k]
        e = np.zeros_like(x)
        e[0] = np.linalg.norm(x)
        v = x - e
        v = v / np.linalg.norm(v)

        H_k = np.eye(n)
        H_k[k:, k:] -= 2.0 * np.outer(v, v)

        R = H_k @ R
        Q = Q @ H_k.T

    return Q, R

# Example Usage
if __name__ == "__main__":
    A = np.array([[1, 1],
                  [1, 2],
                  [1, 3]], dtype=float)

    print("Matrix A:")
    print(A)

    print("\nQR Decomposition using Gram-Schmidt:")
    Q_gs, R_gs = qr_gram_schmidt(A)
    print("Q:")
    print(Q_gs)
    print("R:")
    print(R_gs)

    print("\nQR Decomposition using Householder Reflections:")
    Q_hh, R_hh = qr_householder(A)
    print("Q:")
    print(Q_hh)
    print("R:")
    print(R_hh)